//===--- ASTSelection.cpp - Clang refactoring library ---------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

#include "clang/Tooling/Refactoring/ASTSelection.h"

#include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"

#include "clang/Lex/Lexer.h"

#include "llvm/Support/SaveAndRestore.h"

using namespace clang;

using namespace tooling;

namespace {

CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,

                                    const LangOptions &LangOpts) {

  if (!isa<ObjCImplDecl>(D))

    return CharSourceRange::getTokenRange(D->getSourceRange());

  // Objective-C implementation declarations end at the '@' instead of the 'end'

  // keyword. Use the lexer to find the location right after 'end'.

  SourceRange R = D->getSourceRange();

  SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(

      R.getEnd(), tok::raw_identifier, SM, LangOpts,

      /*SkipTrailingWhitespaceAndNewLine=*/false);

  return LocAfterEnd.isValid()

             ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)

             : 
CharSourceRange::getTokenRange(R)0
;

}

/// Constructs the tree of selected AST nodes that either contain the location

/// of the cursor or overlap with the selection range.

class ASTSelectionFinder

    : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {

public:

  ASTSelectionFinder(SourceRange Selection, FileID TargetFile,

                     const ASTContext &Context)

      : LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),

        SelectionBegin(Selection.getBegin()),

        SelectionEnd(Selection.getBegin() == Selection.getEnd()

                         ? SourceLocation()

                         : Selection.getEnd()),

        TargetFile(TargetFile), Context(Context) {

    // The TU decl is the root of the selected node tree.

    SelectionStack.push_back(

        SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),

                        SourceSelectionKind::None));

  }

  Optional<SelectedASTNode> getSelectedASTNode() {

    assert(SelectionStack.size() == 1 && "stack was not popped");

    SelectedASTNode Result = std::move(SelectionStack.back());

    SelectionStack.pop_back();

    if (Result.Children.empty())

      return None;

    return std::move(Result);

  }

  bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {

    // Avoid traversing the semantic expressions. They should be handled by

    // looking through the appropriate opaque expressions in order to build

    // a meaningful selection tree.

    llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, true);

    return TraverseStmt(E->getSyntacticForm());

  }

  bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {

    if (!LookThroughOpaqueValueExprs)

      return true;

    llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, false);

    return TraverseStmt(E->getSourceExpr());

  }

  bool TraverseDecl(Decl *D) {

    if (isa<TranslationUnitDecl>(D))

      return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);

    if (D->isImplicit())

      return true;

    // Check if this declaration is written in the file of interest.

    const SourceRange DeclRange = D->getSourceRange();

    const SourceManager &SM = Context.getSourceManager();

    SourceLocation FileLoc;

    if (DeclRange.getBegin().isMacroID() && 
!DeclRange.getEnd().isMacroID()0
)

      FileLoc = DeclRange.getEnd();

    else

      FileLoc = SM.getSpellingLoc(DeclRange.getBegin());

    if (SM.getFileID(FileLoc) != TargetFile)

      return true;

    SourceSelectionKind SelectionKind =

        selectionKindFor(getLexicalDeclRange(D, SM, Context.getLangOpts()));

    SelectionStack.push_back(

        SelectedASTNode(DynTypedNode::create(*D), SelectionKind));

    LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);

    popAndAddToSelectionIfSelected(SelectionKind);

    if (DeclRange.getEnd().isValid() &&

        SM.isBeforeInTranslationUnit(SelectionEnd.isValid() ? 
SelectionEnd856

                                                            : 
SelectionBegin21
,

                                     DeclRange.getEnd())) {

      // Stop early when we've reached a declaration after the selection.

      return false;

    }

    return true;

  }

  bool TraverseStmt(Stmt *S) {

    if (!S)

      return true;

    if (auto *Opaque = dyn_cast<OpaqueValueExpr>(S))

      return TraverseOpaqueValueExpr(Opaque);

    // Avoid selecting implicit 'this' expressions.

    if (auto *TE = dyn_cast<CXXThisExpr>(S)) {

      if (TE->isImplicit())

        return true;

    }

    // FIXME (Alex Lorenz): Improve handling for macro locations.

    SourceSelectionKind SelectionKind =

        selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));

    SelectionStack.push_back(

        SelectedASTNode(DynTypedNode::create(*S), SelectionKind));

    LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);

    popAndAddToSelectionIfSelected(SelectionKind);

    return true;

  }

private:

  void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {

    SelectedASTNode Node = std::move(SelectionStack.back());

    SelectionStack.pop_back();

    if (SelectionKind != SourceSelectionKind::None || 
!Node.Children.empty()2.56k
)

      SelectionStack.back().Children.push_back(std::move(Node));

  }

  SourceSelectionKind selectionKindFor(CharSourceRange Range) {

    SourceLocation End = Range.getEnd();

    const SourceManager &SM = Context.getSourceManager();

    if (Range.isTokenRange())

      End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());

    if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))

      return SourceSelectionKind::None;

    if (!SelectionEnd.isValid()) {

      // Do a quick check when the selection is of length 0.

      if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))

        return SourceSelectionKind::ContainsSelection;

      return SourceSelectionKind::None;

    }

    bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);

    bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);

    if (HasStart && 
HasEnd314
)

      return SourceSelectionKind::ContainsSelection;

    if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&

        
SM.isPointWithin(End, SelectionBegin, SelectionEnd)354
)

      return SourceSelectionKind::InsideSelection;

    // Ensure there's at least some overlap with the 'start'/'end' selection

    // types.

    if (HasStart && 
SelectionBegin != End12
)

      return SourceSelectionKind::ContainsSelectionStart;

    if (HasEnd && 
SelectionEnd != Range.getBegin()9
)

      return SourceSelectionKind::ContainsSelectionEnd;

    return SourceSelectionKind::None;

  }

  const SourceLocation SelectionBegin, SelectionEnd;

  FileID TargetFile;

  const ASTContext &Context;

  std::vector<SelectedASTNode> SelectionStack;

  /// Controls whether we can traverse through the OpaqueValueExpr. This is

  /// typically enabled during the traversal of syntactic form for

  /// PseudoObjectExprs.

  bool LookThroughOpaqueValueExprs = false;

};

} // end anonymous namespace

Optional<SelectedASTNode>

clang::tooling::findSelectedASTNodes(const ASTContext &Context,

                                     SourceRange SelectionRange) {

  assert(SelectionRange.isValid() &&

         SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),

                                               SelectionRange.getEnd()) &&

         "Expected a file range");

  FileID TargetFile =

      Context.getSourceManager().getFileID(SelectionRange.getBegin());

  assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==

             TargetFile &&

         "selection range must span one file");

  ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);

  Visitor.TraverseDecl(Context.getTranslationUnitDecl());

  return Visitor.getSelectedASTNode();

}

static const char *selectionKindToString(SourceSelectionKind Kind) {

  switch (Kind) {

  case SourceSelectionKind::None:

    return "none";

  case SourceSelectionKind::ContainsSelection:

    return "contains-selection";

  case SourceSelectionKind::ContainsSelectionStart:

    return "contains-selection-start";

  case SourceSelectionKind::ContainsSelectionEnd:

    return "contains-selection-end";

  case SourceSelectionKind::InsideSelection:

    return "inside";

  }

  llvm_unreachable("invalid selection kind");

}

static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,

                 unsigned Indent = 0) {

  OS.indent(Indent * 2);

  if (const Decl *D = Node.Node.get<Decl>()) {

    OS << D->getDeclKindName() << "Decl";

    if (const auto *ND = dyn_cast<NamedDecl>(D))

      OS << " \"" << ND->getDeclName() << '"';

  } else if (const Stmt *S = Node.Node.get<Stmt>()) {

    OS << S->getStmtClassName();

  }

  OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";

  for (const auto &Child : Node.Children)

    dump(Child, OS, Indent + 1);

}

void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }

/// Returns true if the given node has any direct children with the following

/// selection kind.

///

/// Note: The direct children also include children of direct children with the

/// "None" selection kind.

static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,

                                         SourceSelectionKind Kind) {

  assert(Kind != SourceSelectionKind::None && "invalid predicate!");

  for (const auto &Child : Node.Children) {

    if (Child.SelectionKind == Kind)

      return true;

    if (Child.SelectionKind == SourceSelectionKind::None)

      return hasAnyDirectChildrenWithKind(Child, Kind);

  }

  return false;

}

namespace {

struct SelectedNodeWithParents {

  SelectedASTNode::ReferenceType Node;

  llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;

  /// Canonicalizes the given selection by selecting different related AST nodes

  /// when it makes sense to do so.

  void canonicalize();

};

enum SelectionCanonicalizationAction { KeepSelection, SelectParent };

/// Returns the canonicalization action which should be applied to the

/// selected statement.

SelectionCanonicalizationAction

getSelectionCanonizalizationAction(const Stmt *S, const Stmt *Parent) {

  // Select the parent expression when:

  // - The string literal in ObjC string literal is selected, e.g.:

  //     @"test"   becomes   @"test"

  //      ~~~~~~             ~~~~~~~

  if (isa<StringLiteral>(S) && 
isa<ObjCStringLiteral>(Parent)3
)

    return SelectParent;

  // The entire call should be selected when just the member expression

  // that refers to the method or the decl ref that refers to the function

  // is selected.

  //    f.call(args)  becomes  f.call(args)

  //      ~~~~                 ~~~~~~~~~~~~

  //    func(args)  becomes  func(args)

  //    ~~~~                 ~~~~~~~~~~

  else if (const auto *CE = dyn_cast<CallExpr>(Parent)) {

    if ((isa<MemberExpr>(S) || 
isa<DeclRefExpr>(S)1
) &&

        CE->getCallee()->IgnoreImpCasts() == S)

      return SelectParent;

  }

  // FIXME: Syntactic form -> Entire pseudo-object expr.

  return KeepSelection;

}

} // end anonymous namespace

void SelectedNodeWithParents::canonicalize() {

  const Stmt *S = Node.get().Node.get<Stmt>();

  assert(S && "non statement selection!");

  const Stmt *Parent = Parents[Parents.size() - 1].get().Node.get<Stmt>();

  if (!Parent)

    return;

  // Look through the implicit casts in the parents.

  unsigned ParentIndex = 1;

  for (; (ParentIndex + 1) <= Parents.size() && isa<ImplicitCastExpr>(Parent);

       
++ParentIndex1
) {

    const Stmt *NewParent =

        Parents[Parents.size() - ParentIndex - 1].get().Node.get<Stmt>();

    if (!NewParent)

      break;

    Parent = NewParent;

  }

  switch (getSelectionCanonizalizationAction(S, Parent)) {

  case SelectParent:

    Node = Parents[Parents.size() - ParentIndex];

    for (; ParentIndex != 0; 
--ParentIndex6
)

      Parents.pop_back();

    break;

  case KeepSelection:

    break;

  }

}

/// Finds the set of bottom-most selected AST nodes that are in the selection

/// tree with the specified selection kind.

///

/// For example, given the following selection tree:

///

/// FunctionDecl "f" contains-selection

///   CompoundStmt contains-selection [#1]

///     CallExpr inside

///     ImplicitCastExpr inside

///       DeclRefExpr inside

///     IntegerLiteral inside

///     IntegerLiteral inside

/// FunctionDecl "f2" contains-selection

///   CompoundStmt contains-selection [#2]

///     CallExpr inside

///     ImplicitCastExpr inside

///       DeclRefExpr inside

///     IntegerLiteral inside

///     IntegerLiteral inside

///

/// This function will find references to nodes #1 and #2 when searching for the

/// \c ContainsSelection kind.

static void findDeepestWithKind(

    const SelectedASTNode &ASTSelection,

    llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,

    SourceSelectionKind Kind,

    llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {

  if (ASTSelection.Node.get<DeclStmt>()) {

    // Select the entire decl stmt when any of its child declarations is the

    // bottom-most.

    for (const auto &Child : ASTSelection.Children) {

      if (!hasAnyDirectChildrenWithKind(Child, Kind)) {

        MatchingNodes.push_back(SelectedNodeWithParents{

            std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});

        return;

      }

    }

  } else {

    if (!hasAnyDirectChildrenWithKind(ASTSelection, Kind)) {

      // This node is the bottom-most.

      MatchingNodes.push_back(SelectedNodeWithParents{

          std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});

      return;

    }

  }

  // Search in the children.

  ParentStack.push_back(std::cref(ASTSelection));

  for (const auto &Child : ASTSelection.Children)

    findDeepestWithKind(Child, MatchingNodes, Kind, ParentStack);

  ParentStack.pop_back();

}

static void findDeepestWithKind(

    const SelectedASTNode &ASTSelection,

    llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,

    SourceSelectionKind Kind) {

  llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;

  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);

}

Optional<CodeRangeASTSelection>

CodeRangeASTSelection::create(SourceRange SelectionRange,

                              const SelectedASTNode &ASTSelection) {

  // Code range is selected when the selection range is not empty.

  if (SelectionRange.getBegin() == SelectionRange.getEnd())

    return None;

  llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;

  findDeepestWithKind(ASTSelection, ContainSelection,

                      SourceSelectionKind::ContainsSelection);

  // We are looking for a selection in one body of code, so let's focus on

  // one matching result.

  if (ContainSelection.size() != 1)

    return None;

  SelectedNodeWithParents &Selected = ContainSelection[0];

  if (!Selected.Node.get().Node.get<Stmt>())

    return None;

  const Stmt *CodeRangeStmt = Selected.Node.get().Node.get<Stmt>();

  if (!isa<CompoundStmt>(CodeRangeStmt)) {

    Selected.canonicalize();

    return CodeRangeASTSelection(Selected.Node, Selected.Parents,

                                 /*AreChildrenSelected=*/false);

  }

  // FIXME (Alex L): First selected SwitchCase means that first case statement.

  // is selected actually

  // (See https://github.com/apple/swift-clang & CompoundStmtRange).

  // FIXME (Alex L): Tweak selection rules for compound statements, see:

  // https://github.com/apple/swift-clang/blob/swift-4.1-branch/lib/Tooling/

  // Refactor/ASTSlice.cpp#L513

  // The user selected multiple statements in a compound statement.

  Selected.Parents.push_back(Selected.Node);

  return CodeRangeASTSelection(Selected.Node, Selected.Parents,

                               /*AreChildrenSelected=*/true);

}

static bool isFunctionLikeDeclaration(const Decl *D) {

  // FIXME (Alex L): Test for BlockDecl.

  return isa<FunctionDecl>(D) || 
isa<ObjCMethodDecl>(D)21
;

}

bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {

  bool IsPrevCompound = false;

  // Scan through the parents (bottom-to-top) and check if the selection is

  // contained in a compound statement that's a body of a function/method

  // declaration.

  for (const auto &Parent : llvm::reverse(Parents)) {

    const DynTypedNode &Node = Parent.get().Node;

    if (const auto *D = Node.get<Decl>()) {

      if (isFunctionLikeDeclaration(D))

        return IsPrevCompound;

      // Stop the search at any type declaration to avoid returning true for

      // expressions in type declarations in functions, like:

      // function foo() { struct X {

      //   int m = /*selection:*/ 1 + 2 /*selection end*/; }; };

      if (isa<TypeDecl>(D))

        return false;

    }

    IsPrevCompound = Node.get<CompoundStmt>() != nullptr;

  }

  return false;

}

const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {

  for (const auto &Parent : llvm::reverse(Parents)) {

    const DynTypedNode &Node = Parent.get().Node;

    if (const auto *D = Node.get<Decl>()) {

      if (isFunctionLikeDeclaration(D))

        return D;

    }

  }

  return nullptr;

}