text:
//===--- CSSolver.cpp - Constraint Solver ---------------------------------===//
//
// 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 constraint solver used in the type checker.
//
//===----------------------------------------------------------------------===//
#include "ConstraintSystem.h"
#include "ConstraintGraph.h"
#include "swift/AST/ParameterList.h"
#include "swift/AST/TypeWalker.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/SaveAndRestore.h"
#include <memory>
#include <tuple>

using namespace swift;
using namespace constraints;

//===----------------------------------------------------------------------===//
// Constraint solver statistics
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "Constraint solver overall"
#define JOIN2(X,Y) X##Y
STATISTIC(NumSolutionAttempts, "# of solution attempts");
STATISTIC(TotalNumTypeVariables, "# of type variables created");

#define CS_STATISTIC(Name, Description) \
  STATISTIC(Overall##Name, Description);
#include "ConstraintSolverStats.def"

#undef DEBUG_TYPE
#define DEBUG_TYPE "Constraint solver largest system"
#define CS_STATISTIC(Name, Description) \
  STATISTIC(Largest##Name, Description);
#include "ConstraintSolverStats.def"
STATISTIC(LargestSolutionAttemptNumber, "# of the largest solution attempt");

TypeVariableType *ConstraintSystem::createTypeVariable(
                                     ConstraintLocator *locator,
                                     unsigned options) {
  ++TotalNumTypeVariables;
  auto tv = TypeVariableType::getNew(TC.Context, assignTypeVariableID(),
                                     locator, options);
  addTypeVariable(tv);
  return tv;
}

/// \brief Check whether the given type can be used as a binding for the given
/// type variable.
///
/// \returns the type to bind to, if the binding is okay.
Optional<Type> ConstraintSystem::checkTypeOfBinding(TypeVariableType *typeVar,
                                                    Type type,
                                                    bool *isNilLiteral) {
  if (!type)
    return None;

  // Simplify the type.
  type = simplifyType(type);

  // If the type references the type variable, don't permit the binding.
  SmallVector<TypeVariableType *, 4> referencedTypeVars;
  type->getTypeVariables(referencedTypeVars);
  if (count(referencedTypeVars, typeVar))
    return None;

  // If type variable is not allowed to bind to `lvalue`,
  // let's check if type of potential binding has any
  // type variables, which are allowed to bind to `lvalue`,
  // and postpone such type from consideration.
  if (!typeVar->getImpl().canBindToLValue()) {
    for (auto *typeVar : referencedTypeVars) {
      if (typeVar->getImpl().canBindToLValue())
        return None;
    }
  }

  // If the type is a type variable itself, don't permit the binding.
  if (auto bindingTypeVar = type->getRValueType()->getAs<TypeVariableType>()) {
    if (isNilLiteral) {
      *isNilLiteral = false;

      // Look for a literal-conformance constraint on the type variable.
      SmallVector<Constraint *, 8> constraints;
      getConstraintGraph().gatherConstraints(
          bindingTypeVar, constraints,
          ConstraintGraph::GatheringKind::EquivalenceClass);
      for (auto constraint : constraints) {
        if (constraint->getKind() == ConstraintKind::LiteralConformsTo &&
            constraint->getProtocol()->isSpecificProtocol(
                KnownProtocolKind::ExpressibleByNilLiteral) &&
            simplifyType(constraint->getFirstType())->isEqual(bindingTypeVar)) {
          *isNilLiteral = true;
          break;
        }
      }
    }

    return None;
  }

  // Don't bind to a dependent member type.
  if (type->is<DependentMemberType>()) return None;

  // Okay, allow the binding (with the simplified type).
  return type;
}

Solution ConstraintSystem::finalize(
           FreeTypeVariableBinding allowFreeTypeVariables) {
  // Create the solution.
  Solution solution(*this, CurrentScore);

  // Update the best score we've seen so far.
  if (solverState && !retainAllSolutions()) {
    assert(!solverState->BestScore || CurrentScore <= *solverState->BestScore);
    solverState->BestScore = CurrentScore;
  }

  for (auto tv : TypeVariables) {
    if (getFixedType(tv))
      continue;

    switch (allowFreeTypeVariables) {
    case FreeTypeVariableBinding::Disallow:
      llvm_unreachable("Solver left free type variables");

    case FreeTypeVariableBinding::Allow:
      break;

    case FreeTypeVariableBinding::UnresolvedType:
      assignFixedType(tv, TC.Context.TheUnresolvedType);
      break;
    }
  }

  // For each of the type variables, get its fixed type.
  for (auto tv : TypeVariables) {
    solution.typeBindings[tv] = simplifyType(tv)->reconstituteSugar(false);
  }

  // For each of the overload sets, get its overload choice.
  for (auto resolved = resolvedOverloadSets;
       resolved; resolved = resolved->Previous) {
    solution.overloadChoices[resolved->Locator]
      = { resolved->Choice, resolved->OpenedFullType, resolved->ImpliedType };
  }

  // For each of the constraint restrictions, record it with simplified,
  // canonical types.
  if (solverState) {
    for (auto &restriction : ConstraintRestrictions) {
      using std::get;
      CanType first = simplifyType(get<0>(restriction))->getCanonicalType();
      CanType second = simplifyType(get<1>(restriction))->getCanonicalType();
      solution.ConstraintRestrictions[{first, second}] = get<2>(restriction);
    }
  }

  // For each of the fixes, record it as an operation on the affected
  // expression.
  unsigned firstFixIndex = 0;
  if (solverState && solverState->PartialSolutionScope) {
    firstFixIndex = solverState->PartialSolutionScope->numFixes;
  }
  solution.Fixes.append(Fixes.begin() + firstFixIndex, Fixes.end());

  // Remember all the disjunction choices we made.
  for (auto &choice : DisjunctionChoices) {
    // We shouldn't ever register disjunction choices multiple times,
    // but saving and re-applying solutions can cause us to get
    // multiple entries.  We should use an optimized PartialSolution
    // structure for that use case, which would optimize a lot of
    // stuff here.
    assert(!solution.DisjunctionChoices.count(choice.first) ||
           solution.DisjunctionChoices[choice.first] == choice.second);
    solution.DisjunctionChoices.insert(choice);
  }

  // Remember the opened types.
  for (const auto &opened : OpenedTypes) {
    // We shouldn't ever register opened types multiple times,
    // but saving and re-applying solutions can cause us to get
    // multiple entries.  We should use an optimized PartialSolution
    // structure for that use case, which would optimize a lot of
    // stuff here.
    assert((solution.OpenedTypes.count(opened.first) == 0 ||
            solution.OpenedTypes[opened.first] == opened.second)
            && "Already recorded");
    solution.OpenedTypes.insert(opened);
  }

  // Remember the opened existential types.
  for (const auto &openedExistential : OpenedExistentialTypes) {
    assert(solution.OpenedExistentialTypes.count(openedExistential.first) == 0||
           solution.OpenedExistentialTypes[openedExistential.first]
             == openedExistential.second &&
           "Already recorded");
    solution.OpenedExistentialTypes.insert(openedExistential);
  }

  // Remember the defaulted type variables.
  solution.DefaultedConstraints.insert(DefaultedConstraints.begin(),
                                       DefaultedConstraints.end());

  for (auto &e : CheckedConformances)
    solution.Conformances.push_back({e.first, e.second});

  return solution;
}

void ConstraintSystem::applySolution(const Solution &solution) {
  // Update the score.
  CurrentScore += solution.getFixedScore();

  // Assign fixed types to the type variables solved by this solution.
  llvm::SmallPtrSet<TypeVariableType *, 4>
    knownTypeVariables(TypeVariables.begin(), TypeVariables.end());
  for (auto binding : solution.typeBindings) {
    // If we haven't seen this type variable before, record it now.
    if (knownTypeVariables.insert(binding.first).second)
      TypeVariables.push_back(binding.first);

    // If we don't already have a fixed type for this type variable,
    // assign the fixed type from the solution.
    if (!getFixedType(binding.first) && !binding.second->hasTypeVariable())
      assignFixedType(binding.first, binding.second, /*updateState=*/false);
  }

  // Register overload choices.
  // FIXME: Copy these directly into some kind of partial solution?
  for (auto overload : solution.overloadChoices) {
    resolvedOverloadSets
      = new (*this) ResolvedOverloadSetListItem{resolvedOverloadSets,
                                                Type(),
                                                overload.second.choice,
                                                overload.first,
                                                overload.second.openedFullType,
                                                overload.second.openedType};
  }

  // Register constraint restrictions.
  // FIXME: Copy these directly into some kind of partial solution?
  for (auto restriction : solution.ConstraintRestrictions) {
    ConstraintRestrictions.push_back(
        std::make_tuple(restriction.first.first, restriction.first.second,
                        restriction.second));
  }

  // Register the solution's disjunction choices.
  for (auto &choice : solution.DisjunctionChoices) {
    DisjunctionChoices.push_back(choice);
  }

  // Register the solution's opened types.
  for (const auto &opened : solution.OpenedTypes) {
    OpenedTypes.push_back(opened);
  }

  // Register the solution's opened existential types.
  for (const auto &openedExistential : solution.OpenedExistentialTypes) {
    OpenedExistentialTypes.push_back(openedExistential);
  }

  // Register the defaulted type variables.
  DefaultedConstraints.append(solution.DefaultedConstraints.begin(),
                              solution.DefaultedConstraints.end());

  // Register the conformances checked along the way to arrive to solution.
  for (auto &conformance : solution.Conformances)
    CheckedConformances.push_back(conformance);

  // Register any fixes produced along this path.
  Fixes.append(solution.Fixes.begin(), solution.Fixes.end());
}

/// \brief Restore the type variable bindings to what they were before
/// we attempted to solve this constraint system.
void ConstraintSystem::restoreTypeVariableBindings(unsigned numBindings) {
  auto &savedBindings = *getSavedBindings();
  std::for_each(savedBindings.rbegin(), savedBindings.rbegin() + numBindings,
                [](SavedTypeVariableBinding &saved) {
                  saved.restore();
                });
  savedBindings.erase(savedBindings.end() - numBindings,
                      savedBindings.end());
}

/// \brief Enumerates all of the 'direct' supertypes of the given type.
///
/// The direct supertype S of a type T is a supertype of T (e.g., T < S)
/// such that there is no type U where T < U and U < S.
static SmallVector<Type, 4>
enumerateDirectSupertypes(TypeChecker &tc, Type type) {
  SmallVector<Type, 4> result;

  if (auto tupleTy = type->getAs<TupleType>()) {
    // A tuple that can be constructed from a scalar has a value of that
    // scalar type as its supertype.
    // FIXME: There is a way more general property here, where we can drop
    // one label from the tuple, maintaining the rest.
    int scalarIdx = tupleTy->getElementForScalarInit();
    if (scalarIdx >= 0) {
      auto &elt = tupleTy->getElement(scalarIdx);
      if (elt.isVararg()) // FIXME: Should we keep the name?
        result.push_back(elt.getVarargBaseTy());
      else if (elt.hasName())
        result.push_back(elt.getType());
    }
  }

  if (type->mayHaveSuperclass()) {
    // FIXME: Can also weaken to the set of protocol constraints, but only
    // if there are any protocols that the type conforms to but the superclass
    // does not.

    // If there is a superclass, it is a direct supertype.
    if (auto superclass = tc.getSuperClassOf(type))
      result.push_back(superclass);
  }

  if (!type->isMaterializable())
    result.push_back(type->getWithoutSpecifierType());

  // FIXME: lots of other cases to consider!
  return result;
}

bool ConstraintSystem::simplify(bool ContinueAfterFailures) {
  // While we have a constraint in the worklist, process it.
  while (!ActiveConstraints.empty()) {
    // Grab the next constraint from the worklist.
    auto *constraint = &ActiveConstraints.front();
    ActiveConstraints.pop_front();
    assert(constraint->isActive() && "Worklist constraint is not active?");

    // Simplify this constraint.
    switch (simplifyConstraint(*constraint)) {
    case SolutionKind::Error:
      if (!failedConstraint) {
        failedConstraint = constraint;
      }

      if (TC.getLangOpts().DebugConstraintSolver) {
        auto &log = getASTContext().TypeCheckerDebug->getStream();
        log.indent(solverState ? solverState->depth * 2 : 0)
            << "(failed constraint ";
        constraint->print(log, &getASTContext().SourceMgr);
        log << ")\n";
      }

      if (solverState)
        solverState->retireConstraint(constraint);

      CG.removeConstraint(constraint);
      break;

    case SolutionKind::Solved:
      if (solverState) {
        ++solverState->NumSimplifiedConstraints;

        // This constraint has already been solved; retire it.
        solverState->retireConstraint(constraint);
      }

      // Remove the constraint from the constraint graph.
      CG.removeConstraint(constraint);
      break;

    case SolutionKind::Unsolved:
      if (solverState)
        ++solverState->NumUnsimplifiedConstraints;

      InactiveConstraints.push_back(constraint);
      break;
    }

    // This constraint is not active. We delay this operation until
    // after simplification to avoid re-insertion.
    constraint->setActive(false);

    // Check whether a constraint failed. If so, we're done.
    if (failedConstraint && !ContinueAfterFailures) {
      return true;
    }

    // If the current score is worse than the best score we've seen so far,
    // there's no point in continuing. So don't.
    if (worseThanBestSolution()) {
      return true;
    }
  }

  return false;
}

namespace {

/// \brief Truncate the given small vector to the given new size.
template<typename T>
void truncate(SmallVectorImpl<T> &vec, unsigned newSize) {
  assert(newSize <= vec.size() && "Not a truncation!");
  vec.erase(vec.begin() + newSize, vec.end());
}

} // end anonymous namespace

ConstraintSystem::SolverState::SolverState(ConstraintSystem &cs) : CS(cs) {
  assert(!CS.solverState &&
         "Constraint system should not already have solver state!");
  CS.solverState = this;

  ++NumSolutionAttempts;
  SolutionAttempt = NumSolutionAttempts;

  // If we're supposed to debug a specific constraint solver attempt,
  // turn on debugging now.
  ASTContext &ctx = CS.getTypeChecker().Context;
  LangOptions &langOpts = ctx.LangOpts;
  OldDebugConstraintSolver = langOpts.DebugConstraintSolver;
  if (langOpts.DebugConstraintSolverAttempt &&
      langOpts.DebugConstraintSolverAttempt == SolutionAttempt) {
    langOpts.DebugConstraintSolver = true;
    llvm::raw_ostream &dbgOut = ctx.TypeCheckerDebug->getStream();
    dbgOut << "---Constraint system #" << SolutionAttempt << "---\n";
    CS.print(dbgOut);
  }
}

ConstraintSystem::SolverState::~SolverState() {
  assert((CS.solverState == this) &&
         "Expected constraint system to have this solver state!");
  CS.solverState = nullptr;

  // Restore debugging state.
  LangOptions &langOpts = CS.getTypeChecker().Context.LangOpts;
  langOpts.DebugConstraintSolver = OldDebugConstraintSolver;

  // Write our local statistics back to the overall statistics.
  #define CS_STATISTIC(Name, Description) JOIN2(Overall,Name) += Name;
  #include "ConstraintSolverStats.def"

  // Update the "largest" statistics if this system is larger than the
  // previous one.
  // FIXME: This is not at all thread-safe.
  if (NumStatesExplored > LargestNumStatesExplored.Value) {
    LargestSolutionAttemptNumber.Value = SolutionAttempt-1;
    ++LargestSolutionAttemptNumber;
    #define CS_STATISTIC(Name, Description) \
      JOIN2(Largest,Name).Value = Name-1; \
      ++JOIN2(Largest,Name);
    #include "ConstraintSolverStats.def"
  }
}

ConstraintSystem::SolverScope::SolverScope(ConstraintSystem &cs)
  : cs(cs), CGScope(cs.CG)
{
  ++cs.solverState->depth;

  resolvedOverloadSets = cs.resolvedOverloadSets;
  numTypeVariables = cs.TypeVariables.size();
  numSavedBindings = cs.solverState->savedBindings.size();
  numConstraintRestrictions = cs.ConstraintRestrictions.size();
  numFixes = cs.Fixes.size();
  numDisjunctionChoices = cs.DisjunctionChoices.size();
  numOpenedTypes = cs.OpenedTypes.size();
  numOpenedExistentialTypes = cs.OpenedExistentialTypes.size();
  numDefaultedConstraints = cs.DefaultedConstraints.size();
  numCheckedConformances = cs.CheckedConformances.size();
  PreviousScore = cs.CurrentScore;

  cs.solverState->registerScope(this);
  assert(!cs.failedConstraint && "Unexpected failed constraint!");

  ++cs.solverState->NumStatesExplored;
}

ConstraintSystem::SolverScope::~SolverScope() {
  --cs.solverState->depth;

  // Erase the end of various lists.
  cs.resolvedOverloadSets = resolvedOverloadSets;
  truncate(cs.TypeVariables, numTypeVariables);

  // Restore bindings.
  cs.restoreTypeVariableBindings(cs.solverState->savedBindings.size() -
                                   numSavedBindings);

  // Move any remaining active constraints into the inactive list.
  if (!cs.ActiveConstraints.empty()) {
    for (auto &constraint : cs.ActiveConstraints) {
      constraint.setActive(false);
    }
    cs.InactiveConstraints.splice(cs.InactiveConstraints.end(),
                                  cs.ActiveConstraints);
  }

  // Rollback all of the changes done to constraints by the current scope,
  // e.g. add retired constraints back to the circulation and remove generated
  // constraints introduced by the current scope.
  cs.solverState->rollback(this);

  // Remove any constraint restrictions.
  truncate(cs.ConstraintRestrictions, numConstraintRestrictions);

  // Remove any fixes.
  truncate(cs.Fixes, numFixes);

  // Remove any disjunction choices.
  truncate(cs.DisjunctionChoices, numDisjunctionChoices);

  // Remove any opened types.
  truncate(cs.OpenedTypes, numOpenedTypes);

  // Remove any opened existential types.
  truncate(cs.OpenedExistentialTypes, numOpenedExistentialTypes);

  // Remove any defaulted type variables.
  truncate(cs.DefaultedConstraints, numDefaultedConstraints);

  // Remove any conformances checked along the current path.
  truncate(cs.CheckedConformances, numCheckedConformances);

  // Reset the previous score.
  cs.CurrentScore = PreviousScore;

  // Clear out other "failed" state.
  cs.failedConstraint = nullptr;
}

/// \brief Try each of the given type variable bindings to find solutions
/// to the given constraint system.
///
/// \param depth The depth of the solution stack.
/// \param typeVar The type variable we're binding.
/// \param bindings The initial set of bindings to explore.
/// \param solutions The set of solutions.
///
/// \returns true if there are no solutions.
bool ConstraintSystem::tryTypeVariableBindings(
    unsigned depth, TypeVariableType *typeVar,
    ArrayRef<ConstraintSystem::PotentialBinding> bindings,
    SmallVectorImpl<Solution> &solutions,
    FreeTypeVariableBinding allowFreeTypeVariables) {
  bool anySolved = false;
  llvm::SmallPtrSet<CanType, 4> exploredTypes;
  llvm::SmallPtrSet<TypeBase *, 4> boundTypes;

  SmallVector<PotentialBinding, 4> storedBindings;
  auto &tc = getTypeChecker();
  ++solverState->NumTypeVariablesBound;

  // If we've already explored a lot of potential solutions, bail.
  if (getExpressionTooComplex(solutions))
    return true;

  for (unsigned tryCount = 0; !anySolved && !bindings.empty(); ++tryCount) {
    // Try each of the bindings in turn.
    ++solverState->NumTypeVariableBindings;
    bool sawFirstLiteralConstraint = false;

    if (tc.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(depth * 2) << "Active bindings: ";

      for (auto binding : bindings) {
        log << typeVar->getString() << " := "
            << binding.BindingType->getString() << " ";
      }

      log <<"\n";
    }

    for (const auto &binding : bindings) {
      // If this is a defaultable binding and we have found any solutions,
      // don't explore the default binding.
      if (binding.isDefaultableBinding() && anySolved)
        continue;

      auto type = binding.BindingType;

      // If the type variable can't bind to an lvalue, make sure the
      // type we pick isn't an lvalue.
      if (!typeVar->getImpl().canBindToLValue())
        type = type->getRValueType();

      // Remove parentheses. They're insignificant here.
      type = type->getWithoutParens();

      // If we've already tried this binding, move on.
      if (!boundTypes.insert(type.getPointer()).second)
        continue;

      // Prevent against checking against the same bound generic type
      // over and over again. Doing so means redundant work in the best
      // case. In the worst case, we'll produce lots of duplicate solutions
      // for this constraint system, which is problematic for overload
      // resolution.
      if (type->hasTypeVariable()) {
        auto triedBinding = false;
        if (auto BGT = type->getAs<BoundGenericType>()) {
          for (auto bt : boundTypes) {
            if (auto BBGT = bt->getAs<BoundGenericType>()) {
              if (BGT != BBGT &&
                  BGT->getDecl() == BBGT->getDecl()) {
                triedBinding = true;
                break;
              }
            }
          }
        }

        if (triedBinding)
          continue;
      }

      if (tc.getLangOpts().DebugConstraintSolver) {
        auto &log = getASTContext().TypeCheckerDebug->getStream();
        log.indent(depth * 2)
          << "(trying " << typeVar->getString() << " := " << type->getString()
          << "\n";
      }

      // Try to solve the system with typeVar := type
      ConstraintSystem::SolverScope scope(*this);
      if (binding.DefaultedProtocol) {
        // If we were able to solve this without considering
        // default literals, don't bother looking at default literals.
        if (!sawFirstLiteralConstraint) {
          sawFirstLiteralConstraint = true;
          if (anySolved)
            break;
        }
        type = openUnboundGenericType(type, typeVar->getImpl().getLocator());
        type = type->reconstituteSugar(/*recursive=*/false);
      }

      // FIXME: We want the locator that indicates where the binding came
      // from.
      addConstraint(ConstraintKind::Bind, typeVar, type,
                    typeVar->getImpl().getLocator());

      // If this was from a defaultable binding note that.
      if (binding.isDefaultableBinding()) {
        DefaultedConstraints.push_back(binding.DefaultableBinding);
      }

      if (!solveRec(solutions, allowFreeTypeVariables))
        anySolved = true;

      if (tc.getLangOpts().DebugConstraintSolver) {
        auto &log = getASTContext().TypeCheckerDebug->getStream();
        log.indent(depth * 2) << ")\n";
      }
    }

    // If we found any solution, we're done.
    if (anySolved)
      break;

    // None of the children had solutions, enumerate supertypes and
    // try again.
    SmallVector<PotentialBinding, 4> newBindings;

    // Enumerate the supertypes of each of the types we tried.
    for (auto binding : bindings) {
      const auto type = binding.BindingType;
      if (type->hasError())
        continue;

      // After our first pass, note that we've explored these
      // types.
      if (tryCount == 0)
        exploredTypes.insert(type->getCanonicalType());

      // If we have a protocol with a default type, look for alternative
      // types to the default.
      if (tryCount == 0 && binding.DefaultedProtocol) {
        KnownProtocolKind knownKind
          = *((*binding.DefaultedProtocol)->getKnownProtocolKind());
        for (auto altType : getAlternativeLiteralTypes(knownKind)) {
          if (exploredTypes.insert(altType->getCanonicalType()).second)
            newBindings.push_back({altType, AllowedBindingKind::Subtypes,
                                   binding.DefaultedProtocol});
        }
      }

      // Handle simple subtype bindings.
      if (binding.Kind == AllowedBindingKind::Subtypes &&
          typeVar->getImpl().canBindToLValue() &&
          !type->hasLValueType() &&
          !type->is<InOutType>()) {
        // Try lvalue qualification in addition to rvalue qualification.
        auto subtype = LValueType::get(type);
        if (exploredTypes.insert(subtype->getCanonicalType()).second)
          newBindings.push_back({subtype, binding.Kind, None});
      }

      if (binding.Kind == AllowedBindingKind::Subtypes) {
        if (auto tupleTy = type->getAs<TupleType>()) {
          int scalarIdx = tupleTy->getElementForScalarInit();
          if (scalarIdx >= 0) {
            auto eltType = tupleTy->getElementType(scalarIdx);
            if (exploredTypes.insert(eltType->getCanonicalType()).second)
              newBindings.push_back({eltType, binding.Kind, None});
          }
        }

        // If we were unsuccessful solving for T?, try solving for T.
        if (auto objTy = type->getOptionalObjectType()) {
          if (exploredTypes.insert(objTy->getCanonicalType()).second) {
            // If T is a type variable, only attempt this if both the
            // type variable we are trying bindings for, and the type
            // variable we will attempt to bind, both have the same
            // polarity with respect to being able to bind lvalues.
            if (auto otherTypeVar = objTy->getAs<TypeVariableType>()) {
              if (typeVar->getImpl().canBindToLValue() ==
                  otherTypeVar->getImpl().canBindToLValue()) {
                newBindings.push_back({objTy, binding.Kind, None});
              }
            } else {
              newBindings.push_back({objTy, binding.Kind, None});
            }
          }
        }
      }

      if (binding.Kind != AllowedBindingKind::Supertypes)
        continue;

      for (auto supertype : enumerateDirectSupertypes(getTypeChecker(), type)) {
        // If we're not allowed to try this binding, skip it.
        auto simpleSuper = checkTypeOfBinding(typeVar, supertype);
        if (!simpleSuper)
          continue;

        // If we haven't seen this supertype, add it.
        if (exploredTypes.insert((*simpleSuper)->getCanonicalType()).second)
          newBindings.push_back({*simpleSuper, binding.Kind, None});
      }
    }

    // If we didn't compute any new bindings, we're done.
    if (newBindings.empty())
      break;

    // We have a new set of bindings; use them for our next loop.
    storedBindings = std::move(newBindings);
    bindings = storedBindings;
  }

  return !anySolved;
}

/// \brief Solve the system of constraints.
///
/// \param allowFreeTypeVariables How to bind free type variables in
/// the solution.
///
/// \returns a solution if a single unambiguous one could be found, or None if
/// ambiguous or unsolvable.
Optional<Solution>
ConstraintSystem::solveSingle(FreeTypeVariableBinding allowFreeTypeVariables) {
  SmallVector<Solution, 4> solutions;
  if (solve(solutions, allowFreeTypeVariables) ||
      solutions.size() != 1)
    return Optional<Solution>();

  return std::move(solutions[0]);
}

bool ConstraintSystem::Candidate::solve(
    llvm::SmallDenseSet<OverloadSetRefExpr *> &shrunkExprs) {
  // Don't attempt to solve candidate if there is closure
  // expression involved, because it's handled specially
  // by parent constraint system (e.g. parameter lists).
  bool containsClosure = false;
  E->forEachChildExpr([&](Expr *childExpr) -> Expr * {
    if (isa<ClosureExpr>(childExpr)) {
      containsClosure = true;
      return nullptr;
    }
    return childExpr;
  });

  if (containsClosure)
    return false;

  auto cleanupImplicitExprs = [&](Expr *expr) {
    expr->forEachChildExpr([&](Expr *childExpr) -> Expr * {
      Type type = childExpr->getType();
      if (childExpr->isImplicit() && type && type->hasTypeVariable())
        childExpr->setType(Type());
      return childExpr;
    });
  };

  // Allocate new constraint system for sub-expression.
  ConstraintSystem cs(TC, DC, None);
  cs.baseCS = &BaseCS;

  // Set up expression type checker timer for the candidate.
  cs.Timer.emplace(E, cs);

  // Cleanup after constraint system generation/solving,
  // because it would assign types to expressions, which
  // might interfere with solving higher-level expressions.
  ExprCleaner cleaner(E);

  // Generate constraints for the new system.
  if (auto generatedExpr = cs.generateConstraints(E)) {
    E = generatedExpr;
  } else {
    // Failure to generate constraint system for sub-expression
    // means we can't continue solving sub-expressions.
    cleanupImplicitExprs(E);
    return true;
  }

  // If this candidate is too complex given the number
  // of the domains we have reduced so far, let's bail out early.
  if (isTooComplexGiven(&cs, shrunkExprs))
    return false;

  if (TC.getLangOpts().DebugConstraintSolver) {
    auto &log = cs.getASTContext().TypeCheckerDebug->getStream();
    log << "--- Solving candidate for shrinking at ";
    auto R = E->getSourceRange();
    if (R.isValid()) {
      R.print(log, TC.Context.SourceMgr, /*PrintText=*/ false);
    } else {
      log << "<invalid range>";
    }
    log << " ---\n";

    E->print(log);
    log << '\n';
    cs.print(log);
  }

  // If there is contextual type present, add an explicit "conversion"
  // constraint to the system.
  if (!CT.isNull()) {
    auto constraintKind = ConstraintKind::Conversion;
    if (CTP == CTP_CallArgument)
      constraintKind = ConstraintKind::ArgumentConversion;

    cs.addConstraint(constraintKind, cs.getType(E), CT,
                     cs.getConstraintLocator(E), /*isFavored=*/true);
  }

  // Try to solve the system and record all available solutions.
  llvm::SmallVector<Solution, 2> solutions;
  {
    SolverState state(cs);

    // Use solveRec() instead of solve() in here, because solve()
    // would try to deduce the best solution, which we don't
    // really want. Instead, we want the reduced set of domain choices.
    cs.solveRec(solutions, FreeTypeVariableBinding::Allow);
  }

  if (TC.getLangOpts().DebugConstraintSolver) {
    auto &log = cs.getASTContext().TypeCheckerDebug->getStream();
    if (solutions.empty()) {
      log << "--- No Solutions ---\n";
    } else {
      log << "--- Solutions ---\n";
      for (unsigned i = 0, n = solutions.size(); i != n; ++i) {
        auto &solution = solutions[i];
        log << "--- Solution #" << i << " ---\n";
        solution.dump(log);
      }
    }
  }

  // Record found solutions as suggestions.
  this->applySolutions(solutions, shrunkExprs);

  // Let's double-check if we have any implicit expressions
  // with type variables and nullify their types.
  cleanupImplicitExprs(E);

  // No solutions for the sub-expression means that either main expression
  // needs salvaging or it's inconsistent (read: doesn't have solutions).
  return solutions.empty();
}

void ConstraintSystem::Candidate::applySolutions(
    llvm::SmallVectorImpl<Solution> &solutions,
    llvm::SmallDenseSet<OverloadSetRefExpr *> &shrunkExprs) const {
  // A collection of OSRs with their newly reduced domains,
  // it's domains are sets because multiple solutions can have the same
  // choice for one of the type variables, and we want no duplication.
  llvm::SmallDenseMap<OverloadSetRefExpr *, llvm::SmallSet<ValueDecl *, 2>>
    domains;
  for (auto &solution : solutions) {
    for (auto choice : solution.overloadChoices) {
      // Some of the choices might not have locators.
      if (!choice.getFirst())
        continue;

      auto anchor = choice.getFirst()->getAnchor();
      // Anchor is not available or expression is not an overload set.
      if (!anchor || !isa<OverloadSetRefExpr>(anchor))
        continue;

      auto OSR = cast<OverloadSetRefExpr>(anchor);
      auto overload = choice.getSecond().choice;
      auto type = overload.getDecl()->getInterfaceType();

      // One of the solutions has polymorphic type assigned with one of it's
      // type variables. Such functions can only be properly resolved
      // via complete expression, so we'll have to forget solutions
      // we have already recorded. They might not include all viable overload
      // choices.
      if (type->is<GenericFunctionType>()) {
        return;
      }

      domains[OSR].insert(overload.getDecl());
    }
  }

  // Reduce the domains.
  for (auto &domain : domains) {
    auto OSR = domain.getFirst();
    auto &choices = domain.getSecond();

    // If the domain wasn't reduced, skip it.
    if (OSR->getDecls().size() == choices.size()) continue;

    // Update the expression with the reduced domain.
    MutableArrayRef<ValueDecl *> decls(
                                Allocator.Allocate<ValueDecl *>(choices.size()),
                                choices.size());

    std::uninitialized_copy(choices.begin(), choices.end(), decls.begin());
    OSR->setDecls(decls);

    // Record successfully shrunk expression.
    shrunkExprs.insert(OSR);
  }
}

void ConstraintSystem::shrink(Expr *expr) {
  // Disable the shrink pass when constraint propagation is
  // enabled. They achieve similar effects, and the shrink pass is
  // known to have bad behavior in some cases.
  if (TC.Context.LangOpts.EnableConstraintPropagation)
    return;

  typedef llvm::SmallDenseMap<Expr *, ArrayRef<ValueDecl *>> DomainMap;

  // A collection of original domains of all of the expressions,
  // so they can be restored in case of failure.
  DomainMap domains;

  struct ExprCollector : public ASTWalker {
    Expr *PrimaryExpr;

    // The primary constraint system.
    ConstraintSystem &CS;

    // All of the sub-expressions which are suitable to be solved
    // separately from the main system e.g. binary expressions, collections,
    // function calls, coercions etc.
    llvm::SmallVector<Candidate, 4> Candidates;

    // Counts the number of overload sets present in the tree so far.
    // Note that the traversal is depth-first.
    llvm::SmallVector<std::pair<ApplyExpr *, unsigned>, 4> ApplyExprs;

    // A collection of original domains of all of the expressions,
    // so they can be restored in case of failure.
    DomainMap &Domains;

    ExprCollector(Expr *expr, ConstraintSystem &cs, DomainMap &domains)
        : PrimaryExpr(expr), CS(cs), Domains(domains) {}

    std::pair<bool, Expr *> walkToExprPre(Expr *expr) override {
      // A dictionary expression is just a set of tuples; try to solve ones
      // that have overload sets.
      if (auto collectionExpr = dyn_cast<CollectionExpr>(expr)) {
        visitCollectionExpr(collectionExpr, CS.getContextualType(expr),
                            CS.getContextualTypePurpose());
        // Don't try to walk into the dictionary.
        return {false, expr};
      }

      // Let's not attempt to type-check closures or expressions
      // which constrain closures, because they require special handling
      // when dealing with context and parameters declarations.
      if (isa<ClosureExpr>(expr)) {
        return {false, expr};
      }

      if (auto coerceExpr = dyn_cast<CoerceExpr>(expr)) {
        visitCoerceExpr(coerceExpr);
        return {false, expr};
      }

      if (auto OSR = dyn_cast<OverloadSetRefExpr>(expr)) {
        Domains[OSR] = OSR->getDecls();
      }

      if (auto applyExpr = dyn_cast<ApplyExpr>(expr)) {
        auto func = applyExpr->getFn();
        // Let's record this function application for post-processing
        // as well as if it contains overload set, see walkToExprPost.
        ApplyExprs.push_back(
            {applyExpr, isa<OverloadSetRefExpr>(func) || isa<TypeExpr>(func)});
      }

      return { true, expr };
    }

    /// Determine whether this is an arithmetic expression comprised entirely
    /// of literals.
    static bool isArithmeticExprOfLiterals(Expr *expr) {
      expr = expr->getSemanticsProvidingExpr();

      if (auto prefix = dyn_cast<PrefixUnaryExpr>(expr))
        return isArithmeticExprOfLiterals(prefix->getArg());

      if (auto postfix = dyn_cast<PostfixUnaryExpr>(expr))
        return isArithmeticExprOfLiterals(postfix->getArg());

      if (auto binary = dyn_cast<BinaryExpr>(expr))
        return isArithmeticExprOfLiterals(binary->getArg()->getElement(0)) &&
               isArithmeticExprOfLiterals(binary->getArg()->getElement(1));

      return isa<IntegerLiteralExpr>(expr) || isa<FloatLiteralExpr>(expr);
    }

    Expr *walkToExprPost(Expr *expr) override {
      auto isSrcOfPrimaryAssignment = [&](Expr *expr) -> bool {
        if (auto *AE = dyn_cast<AssignExpr>(PrimaryExpr))
          return expr == AE->getSrc();
        return false;
      };

      if (expr == PrimaryExpr || isSrcOfPrimaryAssignment(expr)) {
        // If this is primary expression and there are no candidates
        // to be solved, let's not record it, because it's going to be
        // solved regardless.
        if (Candidates.empty())
          return expr;

        auto contextualType = CS.getContextualType();
        // If there is a contextual type set for this expression.
        if (!contextualType.isNull()) {
          Candidates.push_back(Candidate(CS, PrimaryExpr, contextualType,
                                         CS.getContextualTypePurpose()));
          return expr;
        }

        // Or it's a function application with other candidates present.
        if (isa<ApplyExpr>(expr)) {
          Candidates.push_back(Candidate(CS, PrimaryExpr));
          return expr;
        }
      }

      if (!isa<ApplyExpr>(expr))
        return expr;

      unsigned numOverloadSets = 0;
      // Let's count how many overload sets do we have.
      while (!ApplyExprs.empty()) {
        auto &application = ApplyExprs.back();
        auto applyExpr = application.first;

        // Add overload sets tracked by current expression.
        numOverloadSets += application.second;
        ApplyExprs.pop_back();

        // We've found the current expression, so record the number of
        // overloads.
        if (expr == applyExpr) {
          ApplyExprs.push_back({applyExpr, numOverloadSets});
          break;
        }
      }

      // If there are fewer than two overloads in the chain
      // there is no point of solving this expression,
      // because we won't be able to reduce its domain.
      if (numOverloadSets > 1 && !isArithmeticExprOfLiterals(expr))
        Candidates.push_back(Candidate(CS, expr));

      return expr;
    }

  private:
    /// \brief Extract type of the element from given collection type.
    ///
    /// \param collection The type of the collection container.
    ///
    /// \returns Null type, ErrorType or UnresolvedType on failure,
    /// properly constructed type otherwise.
    Type extractElementType(Type collection) {
      auto &ctx = CS.getASTContext();
      if (!collection || collection->hasError())
        return collection;

      auto base = collection.getPointer();
      auto isInvalidType = [](Type type) -> bool {
        return type.isNull() || type->hasUnresolvedType() ||
               type->hasError();
      };

      // Array type.
      if (auto array = dyn_cast<ArraySliceType>(base)) {
        auto elementType = array->getBaseType();
        // If base type is invalid let's return error type.
        return elementType;
      }

      // Map or Set or any other associated collection type.
      if (auto boundGeneric = dyn_cast<BoundGenericType>(base)) {
        if (boundGeneric->hasUnresolvedType())
          return boundGeneric;

        llvm::SmallVector<TupleTypeElt, 2> params;
        for (auto &type : boundGeneric->getGenericArgs()) {
          // One of the generic arguments in invalid or unresolved.
          if (isInvalidType(type))
            return type;

          params.push_back(type);
        }

        // If there is just one parameter, let's return it directly.
        if (params.size() == 1)
          return params[0].getType();

        return TupleType::get(params, ctx);
      }

      return Type();
    }

    bool isSuitableCollection(TypeRepr *collectionTypeRepr) {
      // Only generic identifier, array or dictionary.
      switch (collectionTypeRepr->getKind()) {
      case TypeReprKind::GenericIdent:
      case TypeReprKind::Array:
      case TypeReprKind::Dictionary:
        return true;

      default:
        return false;
      }
    }

    void visitCoerceExpr(CoerceExpr *coerceExpr) {
      auto subExpr = coerceExpr->getSubExpr();
      // Coerce expression is valid only if it has sub-expression.
      if (!subExpr) return;

      unsigned numOverloadSets = 0;
      subExpr->forEachChildExpr([&](Expr *childExpr) -> Expr * {
        if (isa<OverloadSetRefExpr>(childExpr)) {
          ++numOverloadSets;
          return childExpr;
        }

        if (auto nestedCoerceExpr = dyn_cast<CoerceExpr>(childExpr)) {
          visitCoerceExpr(nestedCoerceExpr);
          // Don't walk inside of nested coercion expression directly,
          // that is be done by recursive call to visitCoerceExpr.
          return nullptr;
        }

        // If sub-expression we are trying to coerce to type is a collection,
        // let's allow collector discover it with assigned contextual type
        // of coercion, which allows collections to be solved in parts.
        if (auto collectionExpr = dyn_cast<CollectionExpr>(childExpr)) {
          auto castTypeLoc = coerceExpr->getCastTypeLoc();
          auto typeRepr = castTypeLoc.getTypeRepr();

          if (typeRepr && isSuitableCollection(typeRepr)) {
            // Clone representative to avoid modifying in-place,
            // FIXME: We should try and silently resolve the type here,
            // instead of cloning representative.
            auto coercionRepr = typeRepr->clone(CS.getASTContext());
            // Let's try to resolve coercion type from cloned representative.
            auto coercionType = CS.TC.resolveType(coercionRepr, CS.DC,
                                                  TypeResolutionOptions());

            // Looks like coercion type is invalid, let's skip this sub-tree.
            if (coercionType->hasError())
              return nullptr;

            // Visit collection expression inline.
            visitCollectionExpr(collectionExpr, coercionType,
                                CTP_CoerceOperand);
          }
        }

        return childExpr;
      });

      // It's going to be inefficient to try and solve
      // coercion in parts, so let's just make it a candidate directly,
      // if it contains at least a single overload set.

      if (numOverloadSets > 0)
        Candidates.push_back(Candidate(CS, coerceExpr));
    }

    void visitCollectionExpr(CollectionExpr *collectionExpr,
                             Type contextualType = Type(),
                             ContextualTypePurpose CTP = CTP_Unused) {
      // If there is a contextual type set for this collection,
      // let's propagate it to the candidate.
      if (!contextualType.isNull()) {
        auto elementType = extractElementType(contextualType);
        // If we couldn't deduce element type for the collection, let's
        // not attempt to solve it.
        if (!elementType ||
            elementType->hasError() ||
            elementType->hasUnresolvedType())
          return;

        contextualType = elementType;
      }

      for (auto element : collectionExpr->getElements()) {
        unsigned numOverloads = 0;
        element->walk(OverloadSetCounter(numOverloads));

        // There are no overload sets in the element; skip it.
        if (numOverloads == 0)
          continue;

        // Record each of the collection elements, which passed
        // number of overload sets rule, as a candidate for solving
        // with contextual type of the collection.
        Candidates.push_back(Candidate(CS, element, contextualType, CTP));
      }
    }
  };

  ExprCollector collector(expr, *this, domains);

  // Collect all of the binary/unary and call sub-expressions
  // so we can start solving them separately.
  expr->walk(collector);

  llvm::SmallDenseSet<OverloadSetRefExpr *> shrunkExprs;
  for (auto &candidate : collector.Candidates) {
    // If there are no results, let's forget everything we know about the
    // system so far. This actually is ok, because some of the expressions
    // might require manual salvaging.
    if (candidate.solve(shrunkExprs)) {
      // Let's restore all of the original OSR domains for this sub-expression,
      // this means that we can still make forward progress with solving of the
      // top sub-expressions.
      candidate.getExpr()->forEachChildExpr([&](Expr *childExpr) -> Expr * {
        if (auto OSR = dyn_cast<OverloadSetRefExpr>(childExpr)) {
          auto domain = domains.find(OSR);
          if (domain == domains.end())
            return childExpr;

          OSR->setDecls(domain->getSecond());
          shrunkExprs.erase(OSR);
        }

        return childExpr;
      });
    }
  }

  // Once "shrinking" is done let's re-allocate final version of
  // the candidate list to the permanent arena, so it could
  // survive even after primary constraint system is destroyed.
  for (auto &OSR : shrunkExprs) {
    auto choices = OSR->getDecls();
    auto decls = TC.Context.AllocateUninitialized<ValueDecl *>(choices.size());

    std::uninitialized_copy(choices.begin(), choices.end(), decls.begin());
    OSR->setDecls(decls);
  }
}

ConstraintSystem::SolutionKind
ConstraintSystem::solve(Expr *&expr,
                        Type convertType,
                        ExprTypeCheckListener *listener,
                        SmallVectorImpl<Solution> &solutions,
                        FreeTypeVariableBinding allowFreeTypeVariables) {
  if (TC.getLangOpts().DebugConstraintSolver) {
    auto &log = getASTContext().TypeCheckerDebug->getStream();
    log << "---Constraint solving for the expression at ";
    auto R = expr->getSourceRange();
    if (R.isValid()) {
      R.print(log, TC.Context.SourceMgr, /*PrintText=*/ false);
    } else {
      log << "<invalid range>";
    }
    log << "---\n";
  }

  assert(!solverState && "use solveRec for recursive calls");

  // Set up the expression type checker timer.
  Timer.emplace(expr, *this);

  // Try to shrink the system by reducing disjunction domains. This
  // goes through every sub-expression and generate its own sub-system, to
  // try to reduce the domains of those subexpressions.
  shrink(expr);

  // Generate constraints for the main system.
  if (auto generatedExpr = generateConstraints(expr))
    expr = generatedExpr;
  else {
    return SolutionKind::Error;
  }

  // If there is a type that we're expected to convert to, add the conversion
  // constraint.
  if (convertType) {
    auto constraintKind = ConstraintKind::Conversion;
    if (getContextualTypePurpose() == CTP_CallArgument)
      constraintKind = ConstraintKind::ArgumentConversion;

    if (allowFreeTypeVariables == FreeTypeVariableBinding::UnresolvedType) {
      convertType = convertType.transform([&](Type type) -> Type {
        if (type->is<UnresolvedType>())
          return createTypeVariable(getConstraintLocator(expr),
                                    TVO_CanBindToInOut);
        return type;
      });
    }

    addConstraint(constraintKind, getType(expr), convertType,
                  getConstraintLocator(expr), /*isFavored*/ true);
  }

  // Notify the listener that we've built the constraint system.
  if (listener && listener->builtConstraints(*this, expr)) {
    return SolutionKind::Error;
  }

  if (TC.getLangOpts().DebugConstraintSolver) {
    auto &log = getASTContext().TypeCheckerDebug->getStream();
    log << "---Initial constraints for the given expression---\n";
    expr->print(log);
    log << "\n";
    print(log);
  }

  // Try to solve the constraint system using computed suggestions.
  solve(solutions, allowFreeTypeVariables);

  // If there are no solutions let's mark system as unsolved,
  // and solved otherwise even if there are multiple solutions still present.

  // There was a Swift 3 bug that allowed us to return Solved if we
  // had found at least one solution before deciding an expression was
  // "too complex". Maintain that behavior, but for Swift > 3 return
  // Unsolved in these cases.
  auto tooComplex = getExpressionTooComplex(solutions);
  auto unsolved = tooComplex || solutions.empty();

  return unsolved ? SolutionKind::Unsolved : SolutionKind::Solved;
}

bool ConstraintSystem::solve(SmallVectorImpl<Solution> &solutions,
                             FreeTypeVariableBinding allowFreeTypeVariables) {
  // Set up solver state.
  SolverState state(*this);

  // Simplify any constraints left active after constraint generation
  // and optimization. Return if the resulting system has no
  // solutions.
  if (failedConstraint || simplify())
    return true;

  // If the experimental constraint propagation pass is enabled, run it.
  if (TC.Context.LangOpts.EnableConstraintPropagation)
    if (propagateConstraints())
      return true;

  // Solve the system.
  solveRec(solutions, allowFreeTypeVariables);

  // Filter deduced solutions, try to figure out if there is
  // a single best solution to use, if not explicitly disabled
  // by constraint system options.
  if (!retainAllSolutions())
    filterSolutions(solutions);

  // We fail if there is no solution.
  return solutions.empty();
}

bool ConstraintSystem::solveRec(SmallVectorImpl<Solution> &solutions,
                                FreeTypeVariableBinding allowFreeTypeVariables){
  // If we already failed, or simplification fails, we're done.
  if (failedConstraint || simplify()) {
    return true;
  } else {
    assert(ActiveConstraints.empty() && "Active constraints remain?");
  }

  // If there are no constraints remaining, we're done. Save this solution.
  if (InactiveConstraints.empty()) {
    // If this solution is worse than the best solution we've seen so far,
    // skip it.
    if (worseThanBestSolution())
      return true;

    // If any free type variables remain and we're not allowed to have them,
    // fail.
    if (allowFreeTypeVariables == FreeTypeVariableBinding::Disallow &&
        hasFreeTypeVariables())
      return true;

    auto solution = finalize(allowFreeTypeVariables);
    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(solverState->depth * 2)
        << "(found solution " << CurrentScore << ")\n";
    }

    solutions.push_back(std::move(solution));
    return false;
  }

  // Contract the edges of the constraint graph.
  CG.optimize();

  // Compute the connected components of the constraint graph.
  // FIXME: We're seeding typeVars with TypeVariables so that the
  // connected-components algorithm only considers those type variables within
  // our component. There are clearly better ways to do this.
  SmallVector<TypeVariableType *, 16> typeVars(TypeVariables);
  SmallVector<unsigned, 16> components;
  unsigned numComponents = CG.computeConnectedComponents(typeVars, components);

  // If we don't have more than one component, just solve the whole
  // system.
  if (numComponents < 2) {
    SmallVector<Constraint *, 8> disjunctions;
    collectDisjunctions(disjunctions);

    return solveSimplified(selectDisjunction(disjunctions), solutions,
                           allowFreeTypeVariables);
  }

  if (TC.Context.LangOpts.DebugConstraintSolver) {
    auto &log = getASTContext().TypeCheckerDebug->getStream();

    // Verify that the constraint graph is valid.
    CG.verify();

    log << "---Constraint graph---\n";
    CG.print(log);

    log << "---Connected components---\n";
    CG.printConnectedComponents(log);
  }

  // Construct a mapping from type variables and constraints to their
  // owning component.
  llvm::DenseMap<TypeVariableType *, unsigned> typeVarComponent;
  llvm::DenseMap<Constraint *, unsigned> constraintComponent;
  for (unsigned i = 0, n = typeVars.size(); i != n; ++i) {
    // Record the component of this type variable.
    typeVarComponent[typeVars[i]] = components[i];

    // Record the component of each of the constraints.
    for (auto constraint : CG[typeVars[i]].getConstraints())
      constraintComponent[constraint] = components[i];
  }

  // Add the orphaned components to the mapping from constraints to components.
  unsigned firstOrphanedConstraint =
    numComponents - CG.getOrphanedConstraints().size();
  {
    unsigned component = firstOrphanedConstraint;
    for (auto constraint : CG.getOrphanedConstraints())
      constraintComponent[constraint] = component++;
  }

  // Sort the constraints into component buckets based on component number.
  std::unique_ptr<Component[]> buckets(new Component[numComponents]);

  while (!InactiveConstraints.empty()) {
    auto *constraint = &InactiveConstraints.front();
    InactiveConstraints.pop_front();
    buckets[constraintComponent[constraint]].record(constraint);
  }

  // Create component ordering based on the information associated
  // with constraints in each bucket - e.g. number of disjunctions.
  std::vector<unsigned> componentOrdering;
  // First seed the ordering with original indexes of the components.
  for (unsigned component = 0; component != numComponents; ++component)
    componentOrdering.push_back(component);
  // Now sort the components in the ordering based on the scores of the buckets.
  std::sort(
      componentOrdering.begin(), componentOrdering.end(),
      [&](const unsigned &componentA, const unsigned &componentB) -> bool {
        return buckets[componentA] < buckets[componentB];
      });

  // Remove all of the orphaned constraints; we'll introduce them as needed.
  auto allOrphanedConstraints = CG.takeOrphanedConstraints();

  // Function object that returns all constraints placed into buckets
  // back to the list of constraints.
  auto returnAllConstraints = [&] {
    assert(InactiveConstraints.empty() && "Already have constraints?");
    for (unsigned component = 0; component != numComponents; ++component)
      buckets[component].reinstateTo(InactiveConstraints);
    CG.setOrphanedConstraints(std::move(allOrphanedConstraints));
  };

  // Compute the partial solutions produced for each connected component.
  std::unique_ptr<SmallVector<Solution, 4>[]>
    partialSolutions(new SmallVector<Solution, 4>[numComponents]);
  Optional<Score> PreviousBestScore = solverState->BestScore;

  for (auto &component : componentOrdering) {
    assert(InactiveConstraints.empty() &&
           "Some constraints were not transferred?");
    ++solverState->NumComponentsSplit;

    auto &bucket = buckets[component];

    llvm::SmallVector<TypeVariableType *, 16> allTypeVariables
      = std::move(TypeVariables);

    Constraint *orphaned = nullptr;
    if (component < firstOrphanedConstraint) {
      // Collect the type variables that are not part of a different
      // component; this includes type variables that are part of the
      // component as well as already-resolved type variables.
      for (auto typeVar : allTypeVariables) {
        auto known = typeVarComponent.find(typeVar);
        if (known != typeVarComponent.end() && known->second != component)
          continue;

        TypeVariables.push_back(typeVar);
      }
    } else {
      // Get the orphaned constraint.
      orphaned = allOrphanedConstraints[component - firstOrphanedConstraint];
    }
    CG.setOrphanedConstraint(orphaned);

    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(solverState->depth * 2)
          << "(solving component #" << component << "\n";
    }

    // Solve for this component. If it fails, we're done.
    bool failed = bucket.solve(*this, partialSolutions[component],
                               allowFreeTypeVariables);

    if (failed) {
      if (TC.getLangOpts().DebugConstraintSolver) {
        auto &log = getASTContext().TypeCheckerDebug->getStream();
        log.indent(solverState->depth * 2) << "failed component #"
                                           << component << ")\n";
      }

      TypeVariables = std::move(allTypeVariables);
      returnAllConstraints();
      return true;
    }

    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(solverState->depth * 2) << "finished component #"
                                         << component << ")\n";
    }

    assert(!partialSolutions[component].empty() &&" No solutions?");

    // Move the type variables back, clear out constraints; we're
    // ready for the next component.
    TypeVariables = std::move(allTypeVariables);

    // For each of the partial solutions, subtract off the current score.
    // It doesn't contribute.
    for (auto &solution : partialSolutions[component])
      solution.getFixedScore() -= CurrentScore;

    // Restore the previous best score.
    solverState->BestScore = PreviousBestScore;
  }

  // Move the constraints back. The system is back in a normal state.
  returnAllConstraints();

  // When there are multiple partial solutions for a given connected component,
  // rank those solutions to pick the best ones. This limits the number of
  // combinations we need to produce; in the common case, down to a single
  // combination.
  for (unsigned component = 0; component != numComponents; ++component) {
    auto &solutions = partialSolutions[component];
    // If there's a single best solution, keep only that one.
    // Otherwise, the set of solutions will at least have been minimized.
    if (!retainAllSolutions())
      filterSolutions(solutions, /*minimize=*/true);
  }

  // Produce all combinations of partial solutions.
  SmallVector<unsigned, 2> indices(numComponents, 0);
  bool done = false;
  bool anySolutions = false;
  do {
    // Create a new solver scope in which we apply all of the partial
    // solutions.
    SolverScope scope(*this);
    for (unsigned i = 0; i != numComponents; ++i)
      applySolution(partialSolutions[i][indices[i]]);

    // This solution might be worse than the best solution found so far. If so,
    // skip it.
    if (!worseThanBestSolution()) {
      // Finalize this solution.
      auto solution = finalize(allowFreeTypeVariables);
      if (TC.getLangOpts().DebugConstraintSolver) {
        auto &log = getASTContext().TypeCheckerDebug->getStream();
        log.indent(solverState->depth * 2)
          << "(composed solution " << CurrentScore << ")\n";
      }

      // Save this solution.
      solutions.push_back(std::move(solution));

      anySolutions = true;
    }

    // Find the next combination.
    for (unsigned n = numComponents; n > 0; --n) {
      ++indices[n-1];

      // If we haven't run out of solutions yet, we're done.
      if (indices[n-1] < partialSolutions[n-1].size())
        break;

      // If we ran out of solutions at the first position, we're done.
      if (n == 1) {
        done = true;
        break;
      }

      // Zero out the indices from here to the end.
      for (unsigned i = n-1; i != numComponents; ++i)
        indices[i] = 0;
    }
  } while (!done);

  return !anySolutions;
}

/// Whether we should short-circuit a disjunction that already has a
/// solution when we encounter the given constraint.
static bool shortCircuitDisjunctionAt(Constraint *constraint,
                                      Constraint *successfulConstraint,
                                      ASTContext &ctx) {

  // If the successfully applied constraint is favored, we'll consider that to
  // be the "best".
  if (successfulConstraint->isFavored() && !constraint->isFavored()) {
#if !defined(NDEBUG)
    if (successfulConstraint->getKind() == ConstraintKind::BindOverload) {
      auto overloadChoice = successfulConstraint->getOverloadChoice();
      assert((!overloadChoice.isDecl() ||
              !overloadChoice.getDecl()->getAttrs().isUnavailable(ctx)) &&
             "Unavailable decl should not be favored!");
    }
#endif

    return true;
  }

  // Anything without a fix is better than anything with a fix.
  if (constraint->getFix() && !successfulConstraint->getFix())
    return true;

  if (auto restriction = constraint->getRestriction()) {
    // Non-optional conversions are better than optional-to-optional
    // conversions.
    if (*restriction == ConversionRestrictionKind::OptionalToOptional)
      return true;

    // Array-to-pointer conversions are better than inout-to-pointer conversions.
    if (auto successfulRestriction = successfulConstraint->getRestriction()) {
      if (*successfulRestriction == ConversionRestrictionKind::ArrayToPointer
          && *restriction == ConversionRestrictionKind::InoutToPointer)
        return true;
    }
  }

  // Implicit conversions are better than checked casts.
  if (constraint->getKind() == ConstraintKind::CheckedCast)
    return true;

  return false;
}

void ConstraintSystem::collectDisjunctions(
    SmallVectorImpl<Constraint *> &disjunctions) {
  for (auto &constraint : InactiveConstraints) {
    if (constraint.getKind() == ConstraintKind::Disjunction)
      disjunctions.push_back(&constraint);
  }
}

/// \brief Check if the given disjunction choice should be attempted by solver.
static bool shouldSkipDisjunctionChoice(ConstraintSystem &cs,
                                        DisjunctionChoice &choice,
                                        Optional<Score> &bestNonGenericScore) {
  if (choice->isDisabled()) {
    auto &TC = cs.TC;
    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = cs.getASTContext().TypeCheckerDebug->getStream();
      log.indent(cs.solverState->depth)
      << "(skipping ";
      choice->print(log, &TC.Context.SourceMgr);
      log << '\n';
    }

    return true;
  }

  // Don't attempt to solve for generic operators if we already have
  // a non-generic solution.

  // FIXME: Less-horrible but still horrible hack to attempt to
  //        speed things up. Skip the generic operators if we
  //        already have a solution involving non-generic operators,
  //        but continue looking for a better non-generic operator
  //        solution.
  if (bestNonGenericScore && choice.isGenericOperatorOrUnavailable()) {
    auto &score = bestNonGenericScore->Data;
    // Let's skip generic overload choices only in case if
    // non-generic score indicates that there were no forced
    // unwrappings of optional(s) and no unavailable overload
    // choices present in the solution.
    if (score[SK_ForceUnchecked] == 0 && score[SK_Unavailable] == 0)
      return true;
  }

  return false;
}

Constraint *ConstraintSystem::selectDisjunction(
    SmallVectorImpl<Constraint *> &disjunctions) {
  if (disjunctions.empty())
    return nullptr;

  // Pick the smallest disjunction.
  // FIXME: This heuristic isn't great, but it helped somewhat for
  // overload sets.
  auto disjunction = disjunctions[0];
  auto bestSize = disjunction->countActiveNestedConstraints();
  if (bestSize > 2) {
    for (auto contender : llvm::makeArrayRef(disjunctions).slice(1)) {
      unsigned newSize = contender->countActiveNestedConstraints();
      if (newSize < bestSize) {
        bestSize = newSize;
        disjunction = contender;

        if (bestSize == 2)
          break;
      }
    }
  }

  // If there are no active constraints in the disjunction, there is
  // no solution.
  if (bestSize == 0)
    return nullptr;

  return disjunction;
}

bool ConstraintSystem::solveSimplified(
    Constraint *disjunction, SmallVectorImpl<Solution> &solutions,
    FreeTypeVariableBinding allowFreeTypeVariables) {

  auto bestBindings = determineBestBindings();

  // If we have a binding that does not involve type variables, and is
  // not fully bound, or we have no disjunction to attempt instead,
  // go ahead and try the bindings for this type variable.
  if (bestBindings && (!disjunction || (!bestBindings->InvolvesTypeVariables &&
                                        !bestBindings->FullyBound))) {
    return tryTypeVariableBindings(solverState->depth, bestBindings->TypeVar,
                                   bestBindings->Bindings, solutions,
                                   allowFreeTypeVariables);
  }

  // If there are no disjunctions we can't solve this system unless we have
  // free type variables and are allowing them in the solution.
  if (!disjunction) {
    if (allowFreeTypeVariables == FreeTypeVariableBinding::Disallow ||
        !hasFreeTypeVariables())
      return true;

    // If this solution is worse than the best solution we've seen so far,
    // skip it.
    if (worseThanBestSolution())
      return true;

    // If we only have relational or member constraints and are allowing
    // free type variables, save the solution.
    for (auto &constraint : InactiveConstraints) {
      switch (constraint.getClassification()) {
      case ConstraintClassification::Relational:
      case ConstraintClassification::Member:
        continue;
      default:
        return true;
      }
    }

    auto solution = finalize(allowFreeTypeVariables);
    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(solverState->depth * 2) << "(found solution)\n";
    }

    solutions.push_back(std::move(solution));
    return false;
  }

  // Remove this disjunction constraint from the list.
  auto afterDisjunction = InactiveConstraints.erase(disjunction);
  CG.removeConstraint(disjunction);

  Optional<std::pair<DisjunctionChoice, Score>> lastSolvedChoice;
  Optional<Score> bestNonGenericScore;

  ++solverState->NumDisjunctions;
  auto constraints = disjunction->getNestedConstraints();
  // Try each of the constraints within the disjunction.
  for (auto index : indices(constraints)) {
    auto currentChoice =
        DisjunctionChoice(this, disjunction, constraints[index]);
    if (shouldSkipDisjunctionChoice(*this, currentChoice, bestNonGenericScore))
      continue;

    // We already have a solution; check whether we should
    // short-circuit the disjunction.
    if (lastSolvedChoice) {
      auto *lastChoice = lastSolvedChoice->first.getConstraint();
      auto &score = lastSolvedChoice->second;
      bool hasUnavailableOverloads = score.Data[SK_Unavailable] > 0;

      // Attempt to short-circuit disjunction only if
      // score indicates that there are no unavailable
      // overload choices present in the solution.
      if (!hasUnavailableOverloads &&
          shortCircuitDisjunctionAt(&currentChoice, lastChoice,
                                    getASTContext()))
        break;
    }

    // If the expression was deemed "too complex", stop now and salvage.
    if (getExpressionTooComplex(solutions))
      break;

    // Try to solve the system with this option in the disjunction.
    SolverScope scope(*this);
    ++solverState->NumDisjunctionTerms;
    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(solverState->depth)
        << "(assuming ";
      currentChoice->print(log, &TC.Context.SourceMgr);
      log << '\n';
    }

    // If the disjunction requested us to, remember which choice we
    // took for it.
    if (disjunction->shouldRememberChoice()) {
      auto locator = disjunction->getLocator();
      assert(locator && "remembered disjunction doesn't have a locator?");
      DisjunctionChoices.push_back({locator, index});
    }

    if (auto score = currentChoice.solve(solutions, allowFreeTypeVariables)) {
      if (!currentChoice.isGenericOperatorOrUnavailable() &&
          currentChoice.isSymmetricOperator()) {
        if (!bestNonGenericScore || score < bestNonGenericScore)
          bestNonGenericScore = score;
      }

      lastSolvedChoice = {currentChoice, *score};

      // If we see a tuple-to-tuple conversion that succeeded, we're done.
      // FIXME: This should be more general.
      if (auto restriction = currentChoice->getRestriction()) {
        if (*restriction == ConversionRestrictionKind::TupleToTuple)
          break;
      }
    }

    if (TC.getLangOpts().DebugConstraintSolver) {
      auto &log = getASTContext().TypeCheckerDebug->getStream();
      log.indent(solverState->depth) << ")\n";
    }
  }

  // Put the disjunction constraint back in its place.
  InactiveConstraints.insert(afterDisjunction, disjunction);
  CG.addConstraint(disjunction);

  // If we are exiting due to an expression that is too complex, do
  // not allow our caller to continue as if we have been successful.
  auto tooComplex = getExpressionTooComplex(solutions);
  return tooComplex || !lastSolvedChoice;
}

Optional<Score>
DisjunctionChoice::solve(SmallVectorImpl<Solution> &solutions,
                         FreeTypeVariableBinding allowFreeTypeVariables) {
  CS->simplifyDisjunctionChoice(Choice);

  propagateConversionInfo();
  if (CS->solveRec(solutions, allowFreeTypeVariables))
    return None;

  assert (!solutions.empty());

  Score bestScore = solutions.front().getFixedScore();

  if (solutions.size() == 1)
    return bestScore;

  for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
    auto &score = solutions[i].getFixedScore();
    if (score < bestScore)
      bestScore = score;
  }

  return bestScore;
}

bool DisjunctionChoice::isGenericOperatorOrUnavailable() const {
  auto *decl = getOperatorDecl(Choice);
  if (!decl)
    return false;

  auto &ctx = decl->getASTContext();
  if (decl->getAttrs().isUnavailable(ctx))
    return true;

  auto interfaceType = decl->getInterfaceType();
  return interfaceType->is<GenericFunctionType>();
}

bool DisjunctionChoice::isSymmetricOperator() const {
  auto *decl = getOperatorDecl(Choice);
  if (!decl)
    return false;

  auto func = dyn_cast<FuncDecl>(decl);
  auto paramList =
      func->getParameterList(func->getDeclContext()->isTypeContext());
  if (paramList->size() != 2)
    return true;

  auto firstType =
      paramList->get(0)->getInterfaceType()->getWithoutSpecifierType();
  auto secondType =
      paramList->get(1)->getInterfaceType()->getWithoutSpecifierType();
  return firstType->isEqual(secondType);
}

void DisjunctionChoice::propagateConversionInfo() const {
  if (!CS->isExplicitConversionConstraint(Disjunction))
    return;

  auto LHS = Choice->getFirstType();
  auto typeVar = LHS->getAs<TypeVariableType>();
  if (!typeVar)
    return;

  // Use the representative (if any) to lookup constraints
  // and potentially bind the coercion type to.
  typeVar = typeVar->getImpl().getRepresentative(nullptr);

  // If the representative already has a type assigned to it
  // we can't really do anything here.
  if (typeVar->getImpl().getFixedType(nullptr))
    return;

  auto bindings = CS->getPotentialBindings(typeVar);
  if (bindings.InvolvesTypeVariables || bindings.Bindings.size() != 1)
    return;

  auto conversionType = bindings.Bindings[0].BindingType;
  SmallVector<Constraint *, 4> constraints;
  CS->CG.gatherConstraints(typeVar, constraints,
                           ConstraintGraph::GatheringKind::EquivalenceClass);

  bool viableForBinding = true;
  for (auto adjacent : constraints) {
    switch (adjacent->getKind()) {
    case ConstraintKind::Conversion:
    case ConstraintKind::Defaultable:
    case ConstraintKind::ConformsTo:
    case ConstraintKind::LiteralConformsTo:
      break;

    default:
      viableForBinding = false;
      break;
    }
  }

  if (viableForBinding)
    CS->addConstraint(ConstraintKind::Bind, typeVar, conversionType,
                      Choice->getLocator());
}


text:
Transfer Rumors: Liverpool To Sell Daniel Sturridge
by David on January 9, 2016
Several of the Sunday newspapers are running with the story that Jurgen Klopp has seen enough, or maybe that should be has has not seen enough, of striker Daniel Sturridge and that he is looking to see the England striker in the January transfer window for around £25m.
Sturridge has played just 106 minutes of football since Klopp took over from Brendan Rodgers and the Liverpool boss has reportedly become increasingly frustrated with the striker's injury record.
Sturridge has been plagued by injuries for more than 18 months and missed most of last season due to calf and thigh problems.
His season was then ended by hip surgery which also delayed his return to this campaign.
The striker has not played since picking up a hamstring injury against Newcastle at the start of December, but he seemed to be on the way back when he put out on social media he was "Good to go" after the Reds' win over Leicester on Boxing Day.
Klopp immediately called for caution and reaffirmed his desire for Sturridge to complete a mini pre-season to ensure no further set-backs after a series of lengthy lay-offs.
What do you think of Liverpool being willing to listen to offers for Sturridge? It sounds like a manager who wants to raise some cash to buy a striker that he can rely on every to play and score. That is neither Sturridge or Benteke.
Sturridge had that one brilliant season with Suarez when Liverpool finished second in the league but he has failed to stay healthy the rest of the time he has been at Liverpool.

redpajama_set_name: RedPajamaCommonCrawl


text:
HomeBlogFinanceHedge fund firm Millennium to shake up investment operations
Hedge fund firm Millennium to shake up investment operations
Millennium Management, one of the world's biggest hedge fund firms, has unveiled a shake-up of the organisation of its investment operations that will see co-chief investment officer Bobby Jain depart.
Founder Izzy Englander wrote to employees on Tuesday, in a note seen by the Financial Times, saying that the firm, which manages $59bn in assets, will set up a so-called "office of the chief investment officer", which will include two new co-CIOs and the heads of risk management in the asset classes in which the firm trades.
Former Goldman Sachs head of equity trading Paul Russo, who is Millennium's global head of equities risk, will become one of the co-CIOs; the second will be announced shortly.
Jain, who joined Millennium more than six years ago when the firm was managing around $30bn, will relinquish the role of co-chief investment officer. Until the middle of next year, he will help the firm shift to the new organisational structure.
The move follows huge growth in assets at the New York-based firm, a so-called multi-manager fund — with 280 teams of traders running money across a wide range of investment strategies.
Such firms have been among the biggest hedge fund winners of recent years, helped by their diversification and their ability to run hefty bets on winning positions while quickly cutting losing positions.
This has meant that, more than many investment firms, they are heavily reliant on having strong risk management operations in order to limit potential trading losses. Millennium came through the market turmoil of spring 2020, when the coronavirus pandemic began to hit markets, to finish the year up around 26 per cent. This year it is up around 10.3 per cent, despite large falls in equity and bond markets.
"Risk management is central to our organisation and investment process, and will be the primary focus of the office of the CIO," Englander, who is a co-CIO himself as well as being chief executive and chair, wrote in the note.
Last year Millennium created new roles to lead the risk management of the asset classes it trades, hiring Russo, as well as former Goldman partners Jeff Verschleiser as head of credit and mortgage-backed securities risk and Scott Rofey, who is head of rates/macro and commodities risk.
Millennium's strong returns have meant that it has been able to get clients to commit to longer lock-ups for their cash, giving the firm a longer-term and more stable asset base. Late last year it revealed plans to return about $15bn to investors while also raising billions of dollars in a private equity-style format.
The Englander note also said that chief operating officer Ajay Nagpal will take on the role of president.
Millennium declined to comment.
laurence.fletcher@ft.com
Firm fund Hedge investment Millennium Operations shake


The Internet has become the center of not only our personal and social lives, but also our business and professional lives. It is easy for anyone to market, buy, sell, or advise anything or anyone via the Internet. Read on to find out how to come up with an Internet marketing business plan.
Internet marketing refers to online advertisement efforts that employ web-based tools, such as emails and dedicated websites, to market and increase the sales of their clients.
Over the past decade, the number of Internet users has grown exponentially, and it has today became a very lucrative place for advertisement and marketing. Needless to say, Internet marketing is a requirement for any business or service provider these days.
There are several websites out there presently that provide this service. If you would like to venture into the field of Internet marketing and start your own online marketing business, you need to have a solid plan to begin with.
This is one of the most fundamental of its aspects, and is essential for increasing the chances of success of your business. Presented here is a generic business plan for Internet marketing, which you can use to get started in this field.
It is imperative for anyone desirous to start this business to have a good idea about several marketing strategies. It is vital to stay up-to-date with the latest case studies, take overs, and other similar activities. They may not all be Internet related, but they are, nonetheless, required to gain an understanding of the market and its components.
Once you have built a good enough marketing knowledge base, you need to market yourself in order to get clients. You need to use online marketing strategies which would be applicable for small businesses and would help promote your website as well. Google AdSense and Google AdWords would work very well for these.
Next, you need to learn how to set up referrals on Google AdSense and Google AdWords accounts (for potential clients). Before you start working on a project, you should search online (Google) for related and relevant websites and blogs.
This can assist virtual participation and increase online visibility. Further, this can allow linking and back-linking as well. Do make sure, however, that the company which has retained you has provided you with the rights to participate virtually on their behalf.
Start Slow: Many new Internet marketers can be seen working on 10 - 15 projects simultaneously, ultimately ending up completing none of them. Thus, it is advisable to start slow with a limited number or projects and clients, whom you can do justice to. Make sure to finish one project before moving on to the next.
Keep it Simple: While making your website attractive by using a lot of colorful images, animations, and effects may help it get noticed, it will also increase its loading time. It is better, therefore, to keep it simple and elegant.
One idea that works is to view your website from a potential visitor's perceptive, and make it such that it is easily navigable and allows the user to quickly find what he is looking for.
Strategize Wisely: Before taking projects, you need to study the different online marketing tools and techniques and come with a strategic plan of action.
It is important to take note of expert advice, and also use tried and tested methods. At the same time, however, you should also try to come up with an innovative marketing strategy that will work for your purpose.
Generate Traffic: Most marketers feel that once they have a good website, the traffic will automatically come. However, unless you make a proactive effort towards attracting traffic, this is not going to happen. For this, you will need to use one marketing strategy at a time, until you see the traffic flow.
Stick to the Plan: Even though the initial phases of your marketing plan do not generate traffic, it may happen that the final stages do. Hence, once you have begun implementing a plan, you should stick to it until all its phases are completed.
Business ethics are the secret to running a successful business. Make sure that you deliver to your clients what you have promised. This will make them stick with you for a long time, and will even lead to word-of-mouth publicity.
A lot of organizations these days prefer to market and advertise via the web, simply because that is where the whole world is now. Nonetheless, some businesses will not profit from the Internet as much as they would otherwise.
In case of such businesses, you could assist them with online earning options, rather than marketing. This would help you further expand your customer base.
You can use the business plan described to run your own Internet marketing business. Remember that, for being successful in any venture, be it online or offline, one needs to put in a lot of time and effort.
Also, you would surely get there faster if you come up with innovative business ideas. So, go ahead and start working hard on that creative marketing plan of yours, and surely success will follow.


Engineering Science Transfer Program A.S. – Welcome to NCC!
Engineering Science Transfer Program A.S.
The Engineering Science curriculum offers the courses that are required in the first two years of study in many bachelor's degree programs in a variety of engineering disciplines such as Mechanical, Civil, Chemical, Electrical, and Biomedical Engineering. The Engineering Science degree is part of the statewide College of Technology (COT) initiative that is an umbrella for Connecticut's twelve community colleges and six public and private partner universities. Through COT's articulation agreement with partner universities, students who get an Associate degree in Engineering Science (with certain GPA's) can transfer seamlessly at junior level to the following institutions: University of Connecticut, Central Connecticut State University, Fairfield University, University of Hartford, University of New Haven, and Charter Oak State College.
** Pick four courses from CAD 133 , EGR 115, BIO 121 , CHE 122 , MAT 272 , EGR 212 , and EGR 214. At least two courses must be EGR courses.
For transferable electives to the various universities, see the pathway coordinator.


I would say the acting is good across the board. No one hams it's up nor under acts. The actors have grasp of how their characters are suppose to behave in the film. They even muddle through some of the more awkward dialogue far better than actor's of today.
Esmeralda (Maureen O'Hara) – This was O'Hara's American debut and was still fairly new to film but not to acting in general. Despite looking very Irish and not very Gypsyesque, she does well in the role. She plays up concern for her people but she demonstrate a coy side. I don't think the role is particularly demanding on the acting front nor do I think it's the best performance of her long career but it was a great debut for her for American audiences. I will give her credit, she did her own stunts (not just in this film but all her films). The stunts in this film were when Quasimodo swung down to rescue her from the gallows and where he lifted her over his head claiming "sanctuary". The lift was the most dangerous of the two stunts. She and the stunt man where about 40 forty feet off the ground which was cobblestone and without a safety net.
Quasimodo(Charles Laughton) – Laughton excels in the role. Quasimodo is the most technically and psychically demanding role in the film. Laughton shines though all the make-up. He doesn't make Quasimodo morose or monstrous instead he plays the role more pitiable and human. I do enjoy with mannerism especially during his brief reign as King of Fools and after his abdication and ringing the bells with his feet.
Jehan Frollo(Sir Cedric Hardwicke) – Hardwicke's plays Frollo with a restraint manner and never teeters into the fevered obsession that the book Frollo exhibited in the book. However other Frollos have played him in this manner so it's not a huge deal plus Hardwicke's Frollo makes you forget that aspect of Frollo's personality. Despite this restraint there are scenes where you can feel craziness behind the facade of control. Like any second he could lose that control and become raving mad and it would still feel in character.
The other actors Edmond O'Brien, Harry Davenport, Thomas Mitchell, Alan Marshal and Walter Hampden are all good in their respective role and in the case of O'Brien made a great film debut.
The acting is good and there not too much I can really say other than what I've already said without getting into 30's acting conventions.
Over the next couple of posts we'll look at the Mise-en-scene of the film.
So after looking at the plot overview let's review it. The first thing to look at is the script. The script of 1939 version of the Hunchback of Notre Dame was written by Bruno Frank and Sonya Levien. Frank wrote an adaptation and Levien wrote a screenplay based off that adaptation. The thing to keep in mind about Frank's adaptation is that he was a German author, poet, dramatist and humanist of Jewish descent. He fled Germany because he feared the Government and lived in Austria and England before going to America in 1937. He then starting working in Hollywood as a writer. So given the political environment of the late 30's along with Frank's experience it's no wonder that the Hunchback of Notre Dame parallels Europe of the late 30s. Considering Frank's background as an author/poet/humanist it's understandable why Gringoire is co-hero with Quasimodo.
Speaking of Quasimodo and scenes that feature him, most of his lines are pretty much verbatim to what Victor Hugo wrote. The film also likes to insert him wherever it can: Louis commenting on the Bells and asking about the Bell ringer, the girl crying to grandmother about seeing him, scaring Esmeralda away from Notre Dame, confessing to Phoebus' murder, and him alone at the end. Clearly the film compensates for Quasimodo isn't the main character in the book.
One of the major problems with the plot is that because there is this push towards modernity, which Louis and Gringoire represent, there are lot of scenes that are either completely added, like opening scene or added to much larger parts of the film so that Louis and Gringoire can be featured more. Quasimodo's flogging and Esmeralda's trial are good examples. The pillory scene cuts away to other characters and sometimes just random extras, but it mainly cuts to Gringoire and Clopin, who are talking about the truth about beggary and Gringoire wanting to help Quasimodo, so he prolonged in the scene further by seeing Claude. Esmeralda's trial has interjects made by Gringoire pleading for common sense, Quasimodo confessing to the murder, and Louis giving Esmeralda a "Trial by Ordeal" the "ordeal" is more chance, basically she just has to touch the right dagger (Louis) to be freed but she fails. These add on don't add much and if they accomplish anyway it weak character develop at best.
this scene does not have as many ADD-ons as the pillory scene but when Quasimodo comes in it just falls apart and having Louis there makes it worst.
Another big problem is Frollo's obsession/lust for Esmeralda comes off very contrived. He sees her dance, he stares but I don't think he is enchanted by her at that moment. Their discussion in Notre Dame is just there so he can talk to her. He starts by letting his prejudices and superstition about her and her people be known and thne he stares at her breasts for more than a few seconds. And while that part is quite amusing, it seems so forced, it almost like he bored of talking to her. After that the talk takes a dive because they strike an accord over a mutual love of animals, for no explain reason Frollo keeps a dozen cats in his office, I guess this would explain why he took in Quasimodo in the first place. Anyway it seemed that Frollo and Esmeralda could be have friends if Quasimodo haven't scared her and he tried to kidnap her. A side point about the kidnapping, at the point where Esmeralda fled from Notre Dame she apparently lived in sanctuary because she didn't have a city permit and would be arrested for not having one, so seemed like the "kidnapping" was only to take her back to safety. It's good thing the guard who recused her didn't ask for her permit, actually the permit thing is never mention again, it completed its' mission for the plot. Anyway back to the Frollo/Esmeralda dynamic, given his tepid feeling and her lacking of feeling anything towards him, this makes the confession scene odd. Esmeralda and Gringoire are performing and for some weird reason Frollo is hosting. He asks Gringoire if he is ready to perform. When Gringoire is out the way , Frollo makes his move and confesses his confused little feelings. Now prior to this scene Frollo tried exactly once to find Esmeralda, he had all the Gypsy girls in the Court of Miracle arrested and then released because Esmeralda wasn't there. So he didn't shown his powerful obsession/lust, so it hard to buy his torment. Prior to this we know that Esmeralda doesn't have any strong dislike of Frollo, so I don't buy her fear in this scene either. Then she goes off with Phoebus and Frollo kills him again I don't believe he was pushed to murder. Since Frollo is the catalyst that causes the story to take motion, the Frollo/Esmeralda dynamic needs to strong, not there because the it was in the original.
I do like that the theme is old vs new and embraces the sprit of progress, it's a nice change of pace for a Hunchback movie. The cliche theme for Hunchback films is "beauty is on the inside". But the theme does tries to hard it assert itself and competes with original too much. I think the plot suffers because of this and ultimately the the plot and the screenplay are the weakest element of the film.
Next time we'll look at the Mise-en-scene for the movie. see ya then!
The first on the radar is the 1939 version of The Hunchback of Notre Dame . Why start with the 1939 version of The Hunchback of Notre Dame? It's by no means the oldest or even the most well known. The oldest adaptation is from 1836 and the most well known is the Disney version. Which is exactly why I'm starting with the 1939 version. In classic Disney fashion, Disney took cues from this version. For instance if you have read the book but for whatever reason you have only seen the Disney version, you might wonder why is Frollo a Judge? Or why Esmeralda is even in Notre Dame midway the flick? The 1939 version is the first to make Frollo a Judge (to my knowledge) and it is the first in the Notre Dame collection to have Esmeralda enter Notre Dame for either a prayer, safety, or both. (though in 1923 version, Esmeralda enters Notre dame to meet with Phoebus).
The film is well regarded as a fine movie with great performances especially by Charles Laughton as Quasimodo or as the Hunchback as he is credited. It garnered two academy awards nominations for Best Original Music Score and Best Sound and given that 1939 was the year of Gone with the Wind, The Wizard of OZ, and other great movies this is nothing to sneeze at.
The film was produced by RKO Radio Pictures and was made as remake for the 1923 version starting Lon Chaney. As far the bare bone of the original plot ala Victor Hugo and the separation of Frollo's characters by making the younger brother Jehan take on the Lustfulness and the elder Claude as the pious archdeacon of Notre Dame, there is very little similarity between the 1923 and 1939 version. Though the sets look very similar, expect the 1939 version was also meant to one up the 1923 version in lavishness and expansiveness of the mise-en-scene.
Next time we'll dive into the plot of 1939 version.
Hello and Welcome to the Hunchblog of Notre Dame.
This Blog is dedicated to reviewing and analyzing the different adaptations of Victor's Hugo novel Notre Dame de Paris aka The Hunchback of Notre Dame. There are dozens of retelling of the novel ranging from movies, cartoons, musicals, ballets, and operas. Some are considered masterpieces and some are just pain awful. Some are vastly popular and beloved and even more are unknown.
So why review the various adaptations of this particular novel? It's a story that is known throughout the world but at the same time it's misunderstood. This is mainly because the focus has shifted from "Our Lady of Paris"(Esmeralda) to Quasimodo as the main (titular) character. Of course not all the versions put Quasimodo as the main character but more than enough have. Is it a bad thing not to follow the novel faithfully? Should failure to follow the novel at least somewhat means that the version be diminish in the quality of the version? I would say no, even if I'm somewhat of purist on following the source material. But so for the sake of this blog, I'm going to review the adaptation on their own merits and then look at the version against the novel.