TypePtr Type::Coerce(AnalysisResultPtr ar, TypePtr type1, TypePtr type2) {
  if (SameType(type1, type2)) return type1;
  if (type1->m_kindOf == KindOfVariant ||
      type2->m_kindOf == KindOfVariant) return Type::Variant;
  if (type1->m_kindOf > type2->m_kindOf) {
    TypePtr tmp = type1;
    type1 = type2;
    type2 = tmp;
  }
  if (type2->m_kindOf == KindOfSome ||
      type2->m_kindOf == KindOfAny) return type1;

  if (type2->m_kindOf & KindOfAuto) {
    if (type1->mustBe(type2->m_kindOf & ~KindOfAuto)) {
      if (!(type1->m_kindOf & Type::KindOfString)) {
        return type1;
      }
      if (type2->m_kindOf == KindOfAutoSequence) {
        return Type::Sequence;
      }
      return TypePtr(new Type((KindOf)(type2->m_kindOf & ~KindOfAuto)));
    }
    return Type::Variant;
  }

  if (type1->mustBe(KindOfInteger)) {
    if (type2->mustBe(KindOfInteger)) {
      return type2;
    } else if (type2->mustBe(KindOfDouble)) {
      return Type::Numeric;
    }
  }

  if (type1->mustBe(Type::KindOfObject) &&
      type2->mustBe(Type::KindOfObject)) {
    if (type1->m_name.empty()) return type1;
    if (type2->m_name.empty()) return type2;
    ClassScopePtr cls1 = ar->findClass(type1->m_name);
    if (cls1 && !cls1->isRedeclaring() &&
        cls1->derivesFrom(ar, type2->m_name, true, false)) {
      return type2;
    }
    ClassScopePtr cls2 = ar->findClass(type2->m_name);
    if (cls2 && !cls2->isRedeclaring() &&
        cls2->derivesFrom(ar, type1->m_name, true, false)) {
      return type1;
    }
    return Type::Object;
  }

  if (type1->mustBe(type2->m_kindOf)) {
    return type2;
  }

  return Type::Variant;
}

void FunctionScope::setParamSpecs(AnalysisResultPtr ar) {
  if (m_maxParam > 0 && m_stmt) {
    MethodStatementPtr stmt = dynamic_pointer_cast<MethodStatement>(m_stmt);
    ExpressionListPtr params = stmt->getParams();

    for (int i = 0; i < m_maxParam; i++) {
      ParameterExpressionPtr param =
        dynamic_pointer_cast<ParameterExpression>((*params)[i]);
      TypePtr specType = param->getTypeSpec(ar, false);
      if (specType &&
          !specType->is(Type::KindOfSome) &&
          !specType->is(Type::KindOfVariant)) {
        m_paramTypeSpecs[i] = specType;
      }
      ExpressionPtr exp = param->defaultValue();
      if (exp) {
        m_paramDefaults[i] = exp->getText(false, false, ar);
      }
    }
  }
}

void ObjectMethodExpression::outputCPPObject(CodeGenerator &cg,
    AnalysisResultPtr ar) {
  bool isThis = m_object->isThis();
  if (isThis && getFunctionScope()->isStatic()) {
    cg_printf("GET_THIS_ARROW()");
  }

  if (!isThis) {
    if (!m_object->getActualType() ||
        (directVariantProxy(ar) && !m_object->hasCPPTemp())) {
      TypePtr expectedType = m_object->getExpectedType();
      ASSERT(!expectedType || expectedType->is(Type::KindOfObject));
      // Clear m_expectedType to avoid type cast (toObject).
      m_object->setExpectedType(TypePtr());
      m_object->outputCPP(cg, ar);
      m_object->setExpectedType(expectedType);
    } else {
      m_object->outputCPP(cg, ar);
    }
  }
}

void FunctionScope::setReturnType(AnalysisResultPtr ar, TypePtr type) {
  // no change can be made to virtual function's prototype
  if (m_overriding) return;

  if (m_returnType) {
    type = Type::Coerce(ar, m_returnType, type);
    if (type && !Type::SameType(m_returnType, type)) {
      ar->incNewlyInferred();
      if (!ar->isFirstPass()) {
        Logger::Verbose("Corrected function return type %s -> %s",
                        m_returnType->toString().c_str(),
                        type->toString().c_str());
      }
    }
  }
  if (!type->getName().empty()) {
    FileScopePtr fs = getFileScope();
    if (fs) fs->addClassDependency(ar, type->getName());
  }
  m_returnType = type;
}

TypePtr FunctionCall::checkParamsAndReturn(AnalysisResultPtr ar,
                                           TypePtr type, bool coerce,
                                           FunctionScopePtr func,
                                           bool arrayParams) {
#ifdef HPHP_DETAILED_TYPE_INF_ASSERT
  assert(func->hasUser(getScope(), BlockScope::UseKindCaller));
#endif /* HPHP_DETAILED_TYPE_INF_ASSERT */
  ConstructPtr self = shared_from_this();
  TypePtr frt;
  {
    TRY_LOCK(func);
    func->getInferTypesMutex().assertOwnedBySelf();
    assert(!func->inVisitScopes() || getScope() == func);
    frt = func->getReturnType();
  }
  if (!frt) {
    m_voidReturn = true;
    setActualType(TypePtr());
    if (!isUnused() && !type->is(Type::KindOfAny)) {
      if (!hasContext(ReturnContext) &&
          !func->isFirstPass() && !func->isAbstract()) {
        if (Option::WholeProgram || !func->getContainingClass() ||
            func->isStatic() || func->isFinal() || func->isPrivate()) {
          Compiler::Error(Compiler::UseVoidReturn, self);
        }
      }
      if (!Type::IsMappedToVariant(type)) {
        setExpectedType(type);
      }
      m_voidWrapper = true;
    }
  } else {
    m_voidReturn = false;
    m_voidWrapper = false;
    type = checkTypesImpl(ar, type, frt, coerce);
    assert(m_actualType);
  }
  if (arrayParams) {
    m_extraArg = 0;
    (*m_params)[0]->inferAndCheck(ar, Type::Array, false);
  } else {
    m_extraArg = func->inferParamTypes(ar, self, m_params, m_valid);
  }
  m_variableArgument = func->isVariableArgument();
  if (m_valid) {
    m_implementedType.reset();
  } else {
    m_implementedType = Type::Variant;
  }
  assert(type);

  return type;
}

void DeclarationBuilder::visitReturnStatement(Ast *node)
{
    AstVisitor::visitReturnStatement(node);

    if (node->tree->l != nullptr) {
        node->tree = node->tree->l;
        if (!hasCurrentType()) {
            appendProblem(node->tree, i18n("Return statement not within function declaration"));
            return;
        }
        TypePtr<FunctionType> t = currentType<FunctionType>();
        if (!t) { // the case of: a = -> { return 1 }
            return;
        }
        ExpressionVisitor ev(currentContext(), m_editor);
        ev.visitNode(node);
        AbstractType::Ptr rType = t->returnType();
        DUChainWriteLocker wlock;
        t->setReturnType(mergeTypes(ev.lastType(), rType));
    }
}

TypePtr Type::Coerce(AnalysisResultPtr ar, TypePtr type1, TypePtr type2) {
  if (SameType(type1, type2)) return type1;
  if (type1->m_kindOf == KindOfVariant ||
      type2->m_kindOf == KindOfVariant) return Type::Variant;
  if (type1->m_kindOf > type2->m_kindOf) return Coerce(ar, type2, type1);
  if (type2->m_kindOf == KindOfSome ||
      type2->m_kindOf == KindOfAny) return type1;

  if (type1->mustBe(KindOfNumeric) && type2->mustBe(Type::KindOfDouble)) {
    return TypePtr(new Type(KindOfNumeric));
  } else if (type1->mustBe(KindOfNumeric) &&
             type2->mustBe(Type::KindOfNumeric)) {
    return type2;
  } else if (type1->mustBe(Type::KindOfObject) &&
             type2->mustBe(Type::KindOfObject)) {
    if (type1->m_name.empty()) return type1;
    if (type2->m_name.empty()) return type2;
    ClassScopePtr cls1 = ar->findClass(type1->m_name);
     if (cls1 && !cls1->isRedeclaring() &&
        cls1->derivesFrom(ar, type2->m_name, true, false)) {
      return type2;
    }
    ClassScopePtr cls2 = ar->findClass(type2->m_name);
    if (cls2 && !cls2->isRedeclaring() &&
        cls2->derivesFrom(ar, type1->m_name, true, false)) {
      return type1;
    }
  }

  return Type::Variant;
}

void DeclarationAnalyzer::visitExtension(const ExtensionDefPtr& node)
{
    //if(parentNode && parentNode->getNodeType() != NodeType::Program)
    if(ctx->currentFunction || ctx->currentType)
    {
        error(node, Errors::E_A_MAY_ONLY_BE_DECLARED_AT_FILE_SCOPE_1, node->getIdentifier()->getName());
        return;
    }
    if(node->getGenericParametersDef())
    {
        error(node, Errors::E_GENERIC_ARGUMENTS_ARE_NOT_ALLOWED_ON_AN_EXTENSION);
        return;
    }
    TypePtr type = lookupType(node->getIdentifier());
    Type::Category category = type->getCategory();
    if(category == Type::Protocol)
    {
        error(node, Errors::E_PROTOCOL_A_CANNOT_BE_EXTENDED_1, type->getName());
        return;
    }
    if(category != Type::Struct && category != Type::Enum && category != Type::Class)
    {
        error(node, Errors::E_NON_NOMINAL_TYPE_A_CANNOT_BE_EXTENDED_1, node->getIdentifier()->getName());
        return;
    }

    SCOPED_SET(ctx->currentType, type);
    TypePtr extension = Type::newExtension(type);
    symbolRegistry->getFileScope()->addExtension(extension);
    SCOPED_SET(ctx->currentExtension, extension);
    for(const DeclarationPtr& decl : *node)
    {
        if(decl->getNodeType() == NodeType::ValueBindings)
        {
            error(node, Errors::E_EXTENSIONS_MAY_NOT_CONTAIN_STORED_PROPERTIES);
            continue;
        }
        decl->accept(semanticAnalyzer);
    }
}

static void installGlobals(ModulePtr m) {
    m->env = new Env(m);
    vector<TopLevelItemPtr>::iterator i, end;
    for (i = m->topLevelItems.begin(), end = m->topLevelItems.end();
         i != end; ++i) {
        TopLevelItem *x = i->ptr();
        x->env = m->env;
        switch (x->objKind) {
        case ENUM_DECL : {
            EnumDecl *enumer = (EnumDecl *)x;
            TypePtr t = enumType(enumer);
            addGlobal(m, enumer->name, enumer->visibility, t.ptr());
            for (unsigned i = 0 ; i < enumer->members.size(); ++i) {
                EnumMember *member = enumer->members[i].ptr();
                member->index = (int)i;
                member->type = t;
                addGlobal(m, member->name, enumer->visibility, member);
            }
            break;
        }
        case NEW_TYPE_DECL : {
            NewTypeDecl *nt = (NewTypeDecl *)x;
            TypePtr t = newType(nt);
            addGlobal(m, nt->name, nt->visibility, t.ptr());
            break;
        }
        case PROCEDURE : {
            Procedure *proc = (Procedure *)x;
            if (proc->interface != NULL)
                proc->interface->env = m->env;
            // fallthrough
        }
        default :
            if (x->name.ptr())
                addGlobal(m, x->name, x->visibility, x);
            break;
        }
    }
}

void ForEachStatement::inferTypes(AnalysisResultPtr ar) {
  IMPLEMENT_INFER_AND_CHECK_ASSERT(getScope());

  m_array->inferAndCheck(ar, m_ref ? Type::Variant : Type::Array, m_ref);
  if (m_name) {
    m_name->inferAndCheck(ar, Type::Primitive, true);
  }
  m_value->inferAndCheck(ar, Type::Variant, true);
  if (m_ref) {
    TypePtr actualType = m_array->getActualType();
    if (!actualType ||
        actualType->is(Type::KindOfVariant) ||
        actualType->is(Type::KindOfObject)) {
      ar->forceClassVariants(getClassScope(), false, true);
    }
  }
  if (m_stmt) {
    getScope()->incLoopNestedLevel();
    m_stmt->inferTypes(ar);
    getScope()->decLoopNestedLevel();
  }
}

void FunctionContainer::countReturnTypes(
  std::map<std::string, int> &counts,
  const StringToFunctionScopePtrVecMap *redec) {
  for (StringToFunctionScopePtrMap::const_iterator iter =
         m_functions.begin(); iter != m_functions.end(); ++iter) {
    FunctionScopePtr f = iter->second;
    if (f->isLocalRedeclaring()) {
      always_assert(redec);
      for (FunctionScopePtr f: redec->find(iter->first)->second) {
        TypePtr type = f->getReturnType();
        if (type) {
          type->count(counts);
        }
      }
    } else {
      TypePtr type = f->getReturnType();
      if (type) {
        type->count(counts);
      }
    }
  }
}

void Expression::setTypes(AnalysisResultConstPtr ar, TypePtr actualType,
                          TypePtr expectedType) {
  assert(actualType);
  assert(expectedType);

  m_actualType = actualType;
  if (!expectedType->is(Type::KindOfAny) &&
      !expectedType->is(Type::KindOfSome)) {
    // store the expected type if it is not Any nor Some,
    // regardless of the actual type
    m_expectedType = expectedType;
  } else {
    m_expectedType.reset();
  }

  // This is a special case where Type::KindOfObject means any object.
  if (m_expectedType && m_expectedType->is(Type::KindOfObject) &&
      !m_expectedType->isSpecificObject() &&
      m_actualType->isSpecificObject()) {
    m_expectedType.reset();
  }
}

static bool checkCopyElision(FunctionScopePtr func, ExpressionPtr exp) {
  if (!exp->getType()->is(Type::KindOfVariant) || func->isRefReturn()) {
    return false;
  }

  TypePtr imp = exp->getImplementedType();
  if (!imp) imp = exp->getActualType();
  if (!imp || !imp->is(Type::KindOfVariant)) return false;

  if (func->getNRVOFix() && exp->is(Expression::KindOfSimpleVariable)) {
    return true;
  }

  if (FunctionCallPtr fc = dynamic_pointer_cast<FunctionCall>(exp)) {
    FunctionScopePtr fs = fc->getFuncScope();
    if (!fs || fs->isRefReturn()) {
      return true;
    }
  }

  return false;
}

TypePtr ExprDict::reduceToSingleAssertion(const TypePtrIdxPairVec &types)
  const {
  assert(m_available);
  TypePtr ret;
  for (TypePtrIdxPairVec::const_iterator it = types.begin();
       it != types.end(); ++it) {
    assert(it->first);
    if (!BitOps::get_bit(it->second, m_available)) continue;
    if (!ret) ret = it->first;
    else if (!Type::SameType(ret, it->first)) {
      if (ret->is(Type::KindOfObject) &&
          it->first->is(Type::KindOfObject)) {
        // reconcile
        ret = Type::InferredObject(
            m_am.getAnalysisResult(), ret, it->first);
      } else {
        return TypePtr();
      }
    }
  }
  return ret;
}

bool ObjectPropertyExpression::outputCPPObject(CodeGenerator &cg,
                                               AnalysisResultPtr ar,
                                               bool noEvalOnError) {
  if (m_object->isThis()) {
    if (m_valid) {
      if (!m_object->getOriginalClass()) {
        m_valid = false;
      } else {
        FunctionScopeRawPtr fs = m_object->getOriginalFunction();
        if (!fs || fs->isStatic()) {
          m_valid = false;
        } else if (m_object->getOriginalClass() != getClassScope() &&
                   m_object->getOriginalClass()->isRedeclaring()) {
          m_valid = false;
        }
      }
    }
    if (!m_valid) {
      cg_printf("GET_THIS_DOT()");
    }
  } else if (m_valid) {
    TypePtr act;
    if (!m_object->hasCPPTemp() && m_object->getImplementedType() &&
        !Type::SameType(m_object->getImplementedType(),
                         m_object->getActualType())) {
      act = m_object->getActualType();
      m_object->setActualType(m_object->getImplementedType());
      ClassScopePtr cls = ar->findExactClass(shared_from_this(),
                                             act->getName());
      cg_printf("((%s%s*)", Option::ClassPrefix, cls->getId(cg).c_str());
    }
    m_object->outputCPP(cg, ar);
    if (act) {
      if (m_object->getImplementedType()->is(Type::KindOfObject)) {
        cg_printf(".get())");
      } else {
        cg_printf(".getObjectData())");
      }
      m_object->setActualType(act);
    }
    cg_printf("->");
  } else {
    TypePtr t = m_object->getType();
    bool ok = t && (t->is(Type::KindOfObject) || t->is(Type::KindOfVariant));
    if (noEvalOnError && !ok) {
      if (!t || !t->is(Type::KindOfArray)) {
        cg_printf("(");
        if (m_object->outputCPPUnneeded(cg, ar)) cg_printf(", ");
        return true;
      }
    }
    ok = ok || !t;
    if (!ok) cg_printf("Variant(");
    m_object->outputCPP(cg, ar);
    if (!ok) cg_printf(")");
    cg_printf(".");
  }
  return false;
}

static void printStaticOrTupleOfStatics(llvm::raw_ostream &out, TypePtr t) {
    switch (t->typeKind) {
    case STATIC_TYPE : {
        StaticType *st = (StaticType *)t.ptr();
        printName(out, st->obj);
        break;
    }
    case TUPLE_TYPE : {
        TupleType *tt = (TupleType *)t.ptr();
        out << "[";
        for (size_t i = 0; i < tt->elementTypes.size(); ++i) {
            if (i != 0)
                out << ", ";
            printStaticOrTupleOfStatics(out, tt->elementTypes[i]);
        }
        out << "]";
        break;
    }
    default :
        assert(false);
    }
}

bool Type::canAssignTo(const TypePtr &type) const
{
    if(type == nullptr)
        return false;
    TypePtr self = this->self();
    if(equals(self, type))
        return true;
    if(type->getCategory() == Protocol || type->getCategory() == Class)
    {
        if(this->category == Type::Specialized)
            self = innerType;
        if(self->parents.find(type) != parents.end())
        {
            return true;
        }
        return false;
    }
    /*
    if(type->getCategory() != category)
        return false;
    if(category == Tuple)
    {
        //In tuple type, each element type must can be assigned to corresponding element type in given argument
        if(elementTypes.size() != type->elementTypes.size())
            return false;
        auto iter1 = elementTypes.begin();
        auto iter2 = type->elementTypes.begin();
        for(; iter1 != elementTypes.end(); iter1++, iter2++)
        {
            if(!(*iter1)->canAssignTo(*iter2))
            {
                return false;
            }
        }
    }
    */
    return equals(self, type);
}

void MethodStatement::outputCPPStaticMethodWrapper(CodeGenerator &cg,
                                                   AnalysisResultPtr ar,
                                                   const char *cls) {
  if (!m_modifiers->isStatic() || !m_stmt) return;
  FunctionScopePtr funcScope = m_funcScope.lock();
  ar->pushScope(funcScope);
  m_modifiers->outputCPP(cg, ar);
  TypePtr type = funcScope->getReturnType();
  if (type) {
    type->outputCPPDecl(cg, ar);
  } else {
    cg.printf("void");
  }
  cg.printf(" %s%s(", Option::MethodPrefix, m_name.c_str());
  CodeGenerator::Context old = cg.getContext();
  cg.setContext(CodeGenerator::CppStaticMethodWrapper);
  funcScope->outputCPPParamsDecl(cg, ar, m_params, true);
  cg.setContext(old);
  cg.printf(") { %s%s%s(\"%s\"", type ? "return " : "",
            Option::MethodImplPrefix, m_name.c_str(),
            cls);
  if (funcScope->isVariableArgument()) {
    cg.printf(", num_args");
  }
  if (m_params) {
    for (int i = 0; i < m_params->getCount(); i++) {
      ParameterExpressionPtr param =
        dynamic_pointer_cast<ParameterExpression>((*m_params)[i]);
      ASSERT(param);
      cg.printf(", %s%s", Option::VariablePrefix, param->getName().c_str());
    }
  }
  if (funcScope->isVariableArgument()) {
    cg.printf(", args");
  }
  cg.printf("); }\n");
  ar->popScope();
}

/*!
 * Gets the common parent class between current class and rhs with the minimum inheritance distance.
 */
TypePtr Type::getCommonParent(const TypePtr& rhs)
{
    if(rhs == nullptr || this == rhs.get())
        return rhs;
    TypePtr a;
    if(parentType)
        a = parentType->getCommonParent(rhs);

    TypePtr pthis = self();
    TypePtr b = rhs->getCommonParent(parentType);
    if(a && b)
    {
        if(a->inheritantDepth > b->inheritantDepth)
            return a;
        else
            return b;
    }
    if(a)
        return a;
    if(b)
        return b;
    return nullptr;
}

void ObjectMethodExpression::outputCPPObjectCall(CodeGenerator &cg,
                                                 AnalysisResultPtr ar) {
  outputCPPObject(cg, ar);
  bool isThis = m_object->isThis();
  if (!isThis) {
    string objType;
    TypePtr type = m_object->getType();
    if (type->isSpecificObject() && !m_name.empty() && m_valid) {
      objType = type->getName();
      ClassScopePtr cls = ar->findClass(objType);
      objType = cls->getId();
    } else {
      objType = "ObjectData";
    }
    if (m_bindClass) {
      cg_printf("-> BIND_CLASS_ARROW(%s) ", objType.c_str());
    } else {
      cg_printf("->");
    }
  } else if (m_bindClass && m_classScope) {
    cg_printf(" BIND_CLASS_ARROW(%s) ", m_classScope->getId().c_str());
  }
}