bool RemoveNamespaceRewriteVisitor::VisitClassTemplatePartialSpecializationDecl(
       ClassTemplatePartialSpecializationDecl *D)
{
  const Type *Ty = D->getInjectedSpecializationType().getTypePtr();
  TransAssert(Ty && "Bad TypePtr!");
  const TemplateSpecializationType *TST =
    dyn_cast<TemplateSpecializationType>(Ty);
  TransAssert(TST && "Bad TemplateSpecializationType!");

  TemplateName TplName = TST->getTemplateName();
  const TemplateDecl *TplD = TplName.getAsTemplateDecl();
  TransAssert(TplD && "Invalid TemplateDecl!");
  NamedDecl *ND = TplD->getTemplatedDecl();
  TransAssert(ND && "Invalid NamedDecl!");

  const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(ND);
  TransAssert(CXXRD && "Invalid CXXRecordDecl!");

  std::string Name;
  if (ConsumerInstance->getNewName(CXXRD, Name)) {
    const TypeSourceInfo *TyInfo = D->getTypeAsWritten();
    if (!TyInfo)
      return true;
    TypeLoc TyLoc = TyInfo->getTypeLoc();
    SourceLocation LocStart = TyLoc.getBeginLoc();
    TransAssert(LocStart.isValid() && "Invalid Location!");
    ConsumerInstance->TheRewriter.ReplaceText(
      LocStart, CXXRD->getNameAsString().size(), Name);
  }
  return true;
}

SourceLocation TypeLoc::getEndLoc() const {
  TypeLoc Cur = *this;
  TypeLoc Last;
  while (true) {
    switch (Cur.getTypeLocClass()) {
    default:
      if (!Last)
	Last = Cur;
      return Last.getLocalSourceRange().getEnd();
    case Paren:
    case ConstantArray:
    case DependentSizedArray:
    case IncompleteArray:
    case VariableArray:
    case FunctionProto:
    case FunctionNoProto:
      Last = Cur;
      break;
    case Pointer:
    case BlockPointer:
    case MemberPointer:
    case LValueReference:
    case RValueReference:
    case PackExpansion:
      if (!Last)
	Last = Cur;
      break;
    case Qualified:
    case Elaborated:
      break;
    }
    Cur = Cur.getNextTypeLoc();
  }
}

 static bool isEnumRawType(const Decl* D, TypeLoc TL) {
   assert (TL.getType());
   if (auto ED = dyn_cast<EnumDecl>(D)) {
     return ED->hasRawType() && ED->getRawType()->isEqual(TL.getType());
   }
   return false;
 }

bool ReturnVoid::isNonVoidReturnFunction(FunctionDecl *FD)
{
  // Avoid duplications
  if (std::find(ValidFuncDecls.begin(), 
                ValidFuncDecls.end(), FD) != 
      ValidFuncDecls.end())
    return false;

  // this function happen to have a library function, e.g. strcpy,
  // then the type source info won't be available, let's try to
  // get one from the one which is in the source
  if (!FD->getTypeSourceInfo()) {
    const FunctionDecl *FirstFD = FD->getFirstDeclaration();
    FD = NULL;
    for (FunctionDecl::redecl_iterator I = FirstFD->redecls_begin(), 
         E = FirstFD->redecls_end(); I != E; ++I) {
      if ((*I)->getTypeSourceInfo()) {
        FD = (*I);
        break;
      }
    }
    if (!FD)
      return false;
  }
  TypeLoc TLoc = FD->getTypeSourceInfo()->getTypeLoc();
  SourceLocation SLoc = TLoc.getBeginLoc();
  if (SLoc.isInvalid())
    return false;
  QualType RVType = FD->getResultType();
  return !(RVType.getTypePtr()->isVoidType());
}

TemplateArgumentLoc
Sema::getTemplateArgumentPackExpansionPattern(
      TemplateArgumentLoc OrigLoc,
      SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
  const TemplateArgument &Argument = OrigLoc.getArgument();
  assert(Argument.isPackExpansion());
  switch (Argument.getKind()) {
  case TemplateArgument::Type: {
    // FIXME: We shouldn't ever have to worry about missing
    // type-source info!
    TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
    if (!ExpansionTSInfo)
      ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
                                                         Ellipsis);
    PackExpansionTypeLoc Expansion =
        ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
    Ellipsis = Expansion.getEllipsisLoc();

    TypeLoc Pattern = Expansion.getPatternLoc();
    NumExpansions = Expansion.getTypePtr()->getNumExpansions();

    // We need to copy the TypeLoc because TemplateArgumentLocs store a
    // TypeSourceInfo.
    // FIXME: Find some way to avoid the copy?
    TypeLocBuilder TLB;
    TLB.pushFullCopy(Pattern);
    TypeSourceInfo *PatternTSInfo =
        TLB.getTypeSourceInfo(Context, Pattern.getType());
    return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
                               PatternTSInfo);
  }

  case TemplateArgument::Expression: {
    PackExpansionExpr *Expansion
      = cast<PackExpansionExpr>(Argument.getAsExpr());
    Expr *Pattern = Expansion->getPattern();
    Ellipsis = Expansion->getEllipsisLoc();
    NumExpansions = Expansion->getNumExpansions();
    return TemplateArgumentLoc(Pattern, Pattern);
  }

  case TemplateArgument::TemplateExpansion:
    Ellipsis = OrigLoc.getTemplateEllipsisLoc();
    NumExpansions = Argument.getNumTemplateExpansions();
    return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
                               OrigLoc.getTemplateQualifierLoc(),
                               OrigLoc.getTemplateNameLoc());

  case TemplateArgument::Declaration:
  case TemplateArgument::NullPtr:
  case TemplateArgument::Template:
  case TemplateArgument::Integral:
  case TemplateArgument::Pack:
  case TemplateArgument::Null:
    return TemplateArgumentLoc();
  }

  llvm_unreachable("Invalid TemplateArgument Kind!");
}

void RedundantVoidArgCheck::processLambdaExpr(
    const MatchFinder::MatchResult &Result, const LambdaExpr *Lambda) {
  if (Lambda->getLambdaClass()->getLambdaCallOperator()->getNumParams() == 0 &&
      Lambda->hasExplicitParameters()) {
    SourceManager *SM = Result.SourceManager;
    TypeLoc TL = Lambda->getLambdaClass()->getLambdaTypeInfo()->getTypeLoc();
    removeVoidArgumentTokens(Result,
                             {SM->getSpellingLoc(TL.getBeginLoc()),
                              SM->getSpellingLoc(TL.getEndLoc())},
                             "lambda expression");
  }
}

static bool extendedTypeIsPrivate(TypeLoc inheritedType) {
  if (!inheritedType.getType())
    return true;

  SmallVector<ProtocolDecl *, 2> protocols;
  if (!inheritedType.getType()->isAnyExistentialType(protocols)) {
    // Be conservative. We don't know how to deal with other extended types.
    return false;
  }

  return std::all_of(protocols.begin(), protocols.end(), declIsPrivate);
}

static void revertDependentTypeLoc(TypeLoc &tl) {
  // If there's no type representation, there's nothing to revert.
  if (!tl.getTypeRepr())
    return;

  // Don't revert an error type; we've already complained.
  if (tl.wasValidated() && tl.isError())
    return;

  // Make sure we validate the type again.
  tl.setType(Type());
}

void PCHDeclReader::VisitDeclaratorDecl(DeclaratorDecl *DD) {
  VisitValueDecl(DD);
  QualType InfoTy = Reader.GetType(Record[Idx++]);
  if (InfoTy.isNull())
    return;

  DeclaratorInfo *DInfo = Reader.getContext()->CreateDeclaratorInfo(InfoTy);
  TypeLocReader TLR(Reader, Record, Idx);
  for (TypeLoc TL = DInfo->getTypeLoc(); !TL.isNull(); TL = TL.getNextTypeLoc())
    TLR.Visit(TL);
  DD->setDeclaratorInfo(DInfo);
}

void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context, 
                                           SourceLocation TemplateKWLoc, 
                                           TypeLoc TL, 
                                           SourceLocation ColonColonLoc) {
  Representation = NestedNameSpecifier::Create(Context, Representation, 
                                               TemplateKWLoc.isValid(), 
                                               TL.getTypePtr());
  
  // Push source-location info into the buffer.
  SavePointer(TL.getOpaqueData(), Buffer, BufferSize, BufferCapacity);
  SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
}

void PassByValueCheck::check(const MatchFinder::MatchResult &Result) {
  const auto *Ctor = Result.Nodes.getNodeAs<CXXConstructorDecl>("Ctor");
  const auto *ParamDecl = Result.Nodes.getNodeAs<ParmVarDecl>("Param");
  const auto *Initializer =
      Result.Nodes.getNodeAs<CXXCtorInitializer>("Initializer");
  SourceManager &SM = *Result.SourceManager;

  // If the parameter is used or anything other than the copy, do not apply
  // the changes.
  if (!paramReferredExactlyOnce(Ctor, ParamDecl))
    return;

  // If the parameter is trivial to copy, don't move it. Moving a trivivally
  // copyable type will cause a problem with misc-move-const-arg
  if (ParamDecl->getType().isTriviallyCopyableType(*Result.Context)) 
    return;

  auto Diag = diag(ParamDecl->getLocStart(), "pass by value and use std::move");

  // Iterate over all declarations of the constructor.
  for (const ParmVarDecl *ParmDecl : collectParamDecls(Ctor, ParamDecl)) {
    auto ParamTL = ParmDecl->getTypeSourceInfo()->getTypeLoc();
    auto RefTL = ParamTL.getAs<ReferenceTypeLoc>();

    // Do not replace if it is already a value, skip.
    if (RefTL.isNull())
      continue;

    TypeLoc ValueTL = RefTL.getPointeeLoc();
    auto TypeRange = CharSourceRange::getTokenRange(ParmDecl->getLocStart(),
                                                    ParamTL.getLocEnd());
    std::string ValueStr =
        Lexer::getSourceText(
            CharSourceRange::getTokenRange(ValueTL.getSourceRange()), SM,
            Result.Context->getLangOpts())
            .str();
    ValueStr += ' ';
    Diag << FixItHint::CreateReplacement(TypeRange, ValueStr);
  }

  // Use std::move in the initialization list.
  Diag << FixItHint::CreateInsertion(Initializer->getRParenLoc(), ")")
       << FixItHint::CreateInsertion(
              Initializer->getLParenLoc().getLocWithOffset(1), "std::move(");

  if (auto IncludeFixit = Inserter->CreateIncludeInsertion(
          Result.SourceManager->getFileID(Initializer->getSourceLocation()),
          "utility",
          /*IsAngled=*/true)) {
    Diag << *IncludeFixit;
  }
}

bool EmptyStructToIntRewriteVisitor::VisitElaboratedTypeLoc(
       ElaboratedTypeLoc Loc)
{
  const ElaboratedType *ETy = dyn_cast<ElaboratedType>(Loc.getTypePtr());
  const Type *NamedTy = ETy->getNamedType().getTypePtr();
  const RecordType *RDTy = NamedTy->getAs<RecordType>();
  if (!RDTy)
    return true;

  const RecordDecl *RD = RDTy->getDecl();
  TransAssert(RD && "NULL RecordDecl!");
  if (RD->getCanonicalDecl() != ConsumerInstance->TheRecordDecl) {
    return true;
  }

  SourceLocation StartLoc = Loc.getLocStart();
  if (StartLoc.isInvalid())
    return true;
  TypeLoc TyLoc = Loc.getNamedTypeLoc();
  SourceLocation EndLoc = TyLoc.getLocStart();
  if (EndLoc.isInvalid())
    return true;
  EndLoc = EndLoc.getLocWithOffset(-1);
  const char *StartBuf = 
    ConsumerInstance->SrcManager->getCharacterData(StartLoc);
  const char *EndBuf = ConsumerInstance->SrcManager->getCharacterData(EndLoc);
  ConsumerInstance->Rewritten = true;
  // It's possible, e.g., 
  // struct S1 {
  //   struct { } S;
  // };
  // Clang will translate struct { } S to
  // struct {
  // };
  //  struct <anonymous struct ...> S;
  // the last declaration is injected by clang.
  // We need to omit it.
  if (StartBuf > EndBuf) {
    SourceLocation KeywordLoc = Loc.getElaboratedKeywordLoc();
    const llvm::StringRef Keyword = 
      TypeWithKeyword::getKeywordName(ETy->getKeyword());
    ConsumerInstance->TheRewriter.ReplaceText(KeywordLoc, 
                                              Keyword.size(), "int");
    return true;
  }
  
  ConsumerInstance->TheRewriter.RemoveText(SourceRange(StartLoc, EndLoc));
  return true;
}

SourceLocation TypeLoc::getEndLoc() const {
  TypeLoc Cur = *this;
  while (true) {
    switch (Cur.getTypeLocClass()) {
    default:
      break;
    case Qualified:
    case Elaborated:
      Cur = Cur.getNextTypeLoc();
      continue;
    }
    break;
  }
  return Cur.getLocalSourceRange().getEnd();
}

    virtual void run(const MatchFinder::MatchResult &Result) {
        auto *d = Result.Nodes.getNodeAs<CXXConstructorDecl>("stuff");
        if (d) {
            if (d->getNumCtorInitializers() > 0) {
                const CXXCtorInitializer *firstinit = *d->init_begin();
                if (!firstinit->isWritten()) {
                    llvm::errs() << "firstinit not written; skipping\n";
                    return;
                }
                if (firstinit->isBaseInitializer()) {
                    TypeLoc basetypeloc = firstinit->getBaseClassLoc();
                    llvm::errs() << "firstinit as base loc: "
                                 << basetypeloc.getBeginLoc().printToString(
                                     *Result.SourceManager) << "\n";
                }
                SourceLocation initloc = firstinit->getSourceLocation();
                llvm::errs() << "firstinit loc: "
                             << initloc.printToString(*Result.SourceManager) << "\n";
                SourceRange initrange = firstinit->getSourceRange();
                llvm::errs() << "firstinit range from "
                             << initrange.getBegin().printToString(
                                 *Result.SourceManager) << "\n";
                llvm::errs() << "firstinit range to "
                             << initrange.getEnd().printToString(
                                 *Result.SourceManager) << "\n";

                SourceLocation start = firstinit->getLParenLoc();
                llvm::errs() << "firstinit start: "
                             << start.printToString(*Result.SourceManager) << "\n";
                Token tok_id = GetTokenBeforeLocation(start, *Result.Context);
                llvm::errs() << "  tok_id: "
                             << tok_id.getLocation().printToString(
                                 *Result.SourceManager) << "\n";
                Token tok_colon =
                    GetTokenBeforeLocation(tok_id.getLocation(), *Result.Context);
                llvm::errs() << "  tok_colon: "
                             << tok_colon.getLocation().printToString(
                                 *Result.SourceManager) << "\n";

                const CXXCtorInitializer *lastinit = *d->init_rbegin();
                SourceLocation end = lastinit->getRParenLoc();
                llvm::errs() << "lastinit end: "
                             << end.printToString(*Result.SourceManager) << "\n";
                //init->getInit()->dump();
            }
        }
    }

void ObjCMigrateASTConsumer::migrateMethodInstanceType(ASTContext &Ctx,
                                                       ObjCContainerDecl *CDecl,
                                                       ObjCMethodDecl *OM) {
  ObjCInstanceTypeFamily OIT_Family =
    Selector::getInstTypeMethodFamily(OM->getSelector());
  if (OIT_Family == OIT_None)
    return;
  // TODO. Many more to come
  switch (OIT_Family) {
    case OIT_Array:
      break;
    case OIT_Dictionary:
      break;
    default:
      return;
  }
  if (!OM->getResultType()->isObjCIdType())
    return;
  
  ObjCInterfaceDecl *IDecl = dyn_cast<ObjCInterfaceDecl>(CDecl);
  if (!IDecl) {
    if (ObjCCategoryDecl *CatDecl = dyn_cast<ObjCCategoryDecl>(CDecl))
      IDecl = CatDecl->getClassInterface();
    else if (ObjCImplDecl *ImpDecl = dyn_cast<ObjCImplDecl>(CDecl))
      IDecl = ImpDecl->getClassInterface();
  }
  if (!IDecl)
    return;
  
  if (OIT_Family ==  OIT_Array &&
      !IDecl->lookupInheritedClass(&Ctx.Idents.get("NSArray")))
    return;
  else if (OIT_Family == OIT_Dictionary &&
           !IDecl->lookupInheritedClass(&Ctx.Idents.get("NSDictionary")))
    return;
  
  TypeSourceInfo *TSInfo =  OM->getResultTypeSourceInfo();
  TypeLoc TL = TSInfo->getTypeLoc();
  SourceRange R = SourceRange(TL.getBeginLoc(), TL.getEndLoc());
  edit::Commit commit(*Editor);
  std::string ClassString = "instancetype";
  commit.replace(R, ClassString);
  Editor->commit(commit);
}

void CXXScopeSpec::Extend(ASTContext &Context, SourceLocation TemplateKWLoc, 
                          TypeLoc TL, SourceLocation ColonColonLoc) {
  Builder.Extend(Context, TemplateKWLoc, TL, ColonColonLoc);
  if (Range.getBegin().isInvalid())
    Range.setBegin(TL.getBeginLoc());
  Range.setEnd(ColonColonLoc);

  assert(Range == Builder.getSourceRange() &&
         "NestedNameSpecifierLoc range computation incorrect");
}

SourceLocation RewriteUtils::getVarDeclTypeLocEnd(const VarDecl *VD)
{
  TypeLoc VarTypeLoc = VD->getTypeSourceInfo()->getTypeLoc();
  const IdentifierInfo *Id = VD->getType().getBaseTypeIdentifier();

  // handle a special case shown as below:
  // x;
  // *y[];
  // (*z)[];
  // void foo(void) {...}
  // where x implicitly has type of int, whereas y has type of int *
  if (!Id) {
    SourceLocation EndLoc = VD->getLocation();
    const char *Buf = SrcManager->getCharacterData(EndLoc);
    int Offset = -1;
    SourceLocation NewEndLoc = EndLoc.getLocWithOffset(Offset);
    if (!NewEndLoc.isValid())
      return EndLoc;

    Buf--;
    while (isspace(*Buf) || (*Buf == '*') || (*Buf == '(')) {
      Offset--;
      NewEndLoc = EndLoc.getLocWithOffset(Offset);
      if (!NewEndLoc.isValid())
        return EndLoc.getLocWithOffset(Offset+1);

      Buf--;
    }
    return EndLoc.getLocWithOffset(Offset+1);
  }

  TypeLoc NextTL = VarTypeLoc.getNextTypeLoc();
  while (!NextTL.isNull()) {
    VarTypeLoc = NextTL;
    NextTL = NextTL.getNextTypeLoc();
  }

  SourceRange TypeLocRange = VarTypeLoc.getSourceRange();
  SourceLocation EndLoc = getEndLocationFromBegin(TypeLocRange);
  TransAssert(EndLoc.isValid() && "Invalid EndLoc!");

  const Type *Ty = VarTypeLoc.getTypePtr();

  // I am not sure why, but for a declaration like below:
  //   unsigned int a; (or long long a;)
  // TypeLoc.getBeginLoc() returns the position of 'u'
  // TypeLoc.getEndLoc() also returns the position of 'u'
  // The size of TypeLoc.getSourceRange() is 8, which is the 
  // length of "unsigned"
  // Then we are getting trouble, because now EndLoc is right 
  // after 'd', but we need it points to the location after "int".
  // skipPossibleTypeRange corrects the above deviation
  // Or am I doing something horrible here?
  EndLoc = skipPossibleTypeRange(Ty, EndLoc, VD->getLocation());
  return EndLoc;
}

bool IndexSwiftASTWalker::passRelatedType(const TypeLoc &Ty) {
  if (IdentTypeRepr *T = dyn_cast_or_null<IdentTypeRepr>(Ty.getTypeRepr())) {
    auto Comps = T->getComponentRange();
    if (auto NTD = dyn_cast_or_null<NominalTypeDecl>(
                     Comps.back()->getBoundDecl())) {
      if (!passRelated(NTD, Comps.back()->getIdLoc()))
        return false;
    }

    return true;
  }

  if (Ty.getType()) {
    if (auto nominal = dyn_cast_or_null<NominalTypeDecl>(
                         Ty.getType()->getDirectlyReferencedTypeDecl()))
      if (!passRelated(nominal, Ty.getLoc()))
        return false;
  }

  return true;
}

void IndexingContext::indexTypeLoc(TypeLoc TL,
                                   const NamedDecl *Parent,
                                   const DeclContext *DC,
                                   bool isBase,
                                   bool isIBType) {
  if (TL.isNull())
    return;

  if (!DC)
    DC = Parent->getLexicalDeclContext();
  TypeIndexer(*this, Parent, DC, isBase, isIBType).TraverseTypeLoc(TL);
}

CXCursor cxcursor::getTypeRefCursor(CXCursor cursor) {
    if (cursor.kind != CXCursor_CallExpr)
        return cursor;

    if (cursor.xdata == 0)
        return cursor;

    const Expr *E = getCursorExpr(cursor);
    TypeSourceInfo *Type = 0;
    if (const CXXUnresolvedConstructExpr *
            UnCtor = dyn_cast<CXXUnresolvedConstructExpr>(E)) {
        Type = UnCtor->getTypeSourceInfo();
    } else if (const CXXTemporaryObjectExpr *Tmp =
                   dyn_cast<CXXTemporaryObjectExpr>(E)) {
        Type = Tmp->getTypeSourceInfo();
    }

    if (!Type)
        return cursor;

    CXTranslationUnit TU = getCursorTU(cursor);
    QualType Ty = Type->getType();
    TypeLoc TL = Type->getTypeLoc();
    SourceLocation Loc = TL.getBeginLoc();

    if (const ElaboratedType *ElabT = Ty->getAs<ElaboratedType>()) {
        Ty = ElabT->getNamedType();
        ElaboratedTypeLoc ElabTL = TL.castAs<ElaboratedTypeLoc>();
        Loc = ElabTL.getNamedTypeLoc().getBeginLoc();
    }

    if (const TypedefType *Typedef = Ty->getAs<TypedefType>())
        return MakeCursorTypeRef(Typedef->getDecl(), Loc, TU);
    if (const TagType *Tag = Ty->getAs<TagType>())
        return MakeCursorTypeRef(Tag->getDecl(), Loc, TU);
    if (const TemplateTypeParmType *TemplP = Ty->getAs<TemplateTypeParmType>())
        return MakeCursorTypeRef(TemplP->getDecl(), Loc, TU);

    return cursor;
}