Rename.cpp | Explore in Territory

//===--- Rename.cpp - Symbol-rename refactorings -----------------*- C++-*-===//
//
// 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 "refactor/Rename.h"
#include "AST.h"
#include "FindTarget.h"
#include "ParsedAST.h"
#include "Selection.h"
#include "SourceCode.h"
#include "index/SymbolCollector.h"
#include "support/Logger.h"
#include "support/Trace.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTTypeTraits.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/ParentMapContext.h"
#include "clang/AST/Stmt.h"
#include "clang/Basic/CharInfo.h"
#include "clang/Basic/LLVM.h"
#include "clang/Basic/SourceLocation.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/JSON.h"
#include <algorithm>
#include <optional>

namespace clang {
namespace clangd {
namespace {

std::optional<std::string> filePath(const SymbolLocation &Loc,
                                    llvm::StringRef HintFilePath) { … }

// Returns true if the given location is expanded from any macro body.
bool isInMacroBody(const SourceManager &SM, SourceLocation Loc) { … }

// Canonical declarations help simplify the process of renaming. Examples:
// - Template's canonical decl is the templated declaration (i.e.
//   ClassTemplateDecl is canonicalized to its child CXXRecordDecl,
//   FunctionTemplateDecl - to child FunctionDecl)
// - Given a constructor/destructor, canonical declaration is the parent
//   CXXRecordDecl because we want to rename both type name and its ctor/dtor.
// - All specializations are canonicalized to the primary template. For example:
//
//    template <typename T, int U>
//    bool Foo = true; (1)
//
//    template <typename T>
//    bool Foo<T, 0> = true; (2)
//
//    template <>
//    bool Foo<int, 0> = true; (3)
//
// Here, both partial (2) and full (3) specializations are canonicalized to (1)
// which ensures all three of them are renamed.
const NamedDecl *canonicalRenameDecl(const NamedDecl *D) { … }

// Some AST nodes can reference multiple declarations. We try to pick the
// relevant one to rename here.
const NamedDecl *pickInterestingTarget(const NamedDecl *D) { … }

llvm::DenseSet<const NamedDecl *> locateDeclAt(ParsedAST &AST,
                                               SourceLocation TokenStartLoc) { … }

void filterRenameTargets(llvm::DenseSet<const NamedDecl *> &Decls) { … }

// By default, we exclude symbols from system headers and protobuf symbols as
// renaming these symbols would change system/generated files which are unlikely
// to be good candidates for modification.
bool isExcluded(const NamedDecl &RenameDecl) { … }

enum class ReasonToReject { … };

std::optional<ReasonToReject> renameable(const NamedDecl &RenameDecl,
                                         StringRef MainFilePath,
                                         const SymbolIndex *Index,
                                         const RenameOptions &Opts) { … }

llvm::Error makeError(ReasonToReject Reason) { … }

// Return all rename occurrences in the main file.
std::vector<SourceLocation> findOccurrencesWithinFile(ParsedAST &AST,
                                                      const NamedDecl &ND) { … }

// Detect name conflict with othter DeclStmts in the same enclosing scope.
const NamedDecl *lookupSiblingWithinEnclosingScope(ASTContext &Ctx,
                                                   const NamedDecl &RenamedDecl,
                                                   StringRef NewName) { … }

// Lookup the declarations (if any) with the given Name in the context of
// RenameDecl.
const NamedDecl *lookupSiblingsWithinContext(ASTContext &Ctx,
                                             const NamedDecl &RenamedDecl,
                                             llvm::StringRef NewName) { … }

const NamedDecl *lookupSiblingWithName(ASTContext &Ctx,
                                       const NamedDecl &RenamedDecl,
                                       llvm::StringRef NewName) { … }

struct InvalidName { … };
std::string toString(InvalidName::Kind K) { … }

llvm::Error makeError(InvalidName Reason) { … }

static bool mayBeValidIdentifier(llvm::StringRef Ident, bool AllowColon) { … }

std::string getName(const NamedDecl &RenameDecl) { … }

// Check if we can rename the given RenameDecl into NewName.
// Return details if the rename would produce a conflict.
llvm::Error checkName(const NamedDecl &RenameDecl, llvm::StringRef NewName,
                      llvm::StringRef OldName) { … }

bool isSelectorLike(const syntax::Token &Cur, const syntax::Token &Next) { … }

bool isMatchingSelectorName(const syntax::Token &Cur, const syntax::Token &Next,
                            const SourceManager &SM,
                            llvm::StringRef SelectorName) { … }

// Scan through Tokens to find ranges for each selector fragment in Sel assuming
// its first segment is located at Tokens.front().
// The search will terminate upon seeing Terminator or a ; at the top level.
std::optional<SymbolRange>
findAllSelectorPieces(llvm::ArrayRef<syntax::Token> Tokens,
                      const SourceManager &SM, Selector Sel,
                      tok::TokenKind Terminator) { … }

/// Collects all ranges of the given identifier/selector in the source code.
///
/// If a selector is given, this does a full lex of the given source code in
/// order to identify all selector fragments (e.g. in method exprs/decls) since
/// they are non-contiguous.
std::vector<SymbolRange> collectRenameIdentifierRanges(
    llvm::StringRef Identifier, llvm::StringRef Content,
    const LangOptions &LangOpts, std::optional<Selector> Selector) { … }

clangd::Range tokenRangeForLoc(ParsedAST &AST, SourceLocation TokLoc,
                               const SourceManager &SM,
                               const LangOptions &LangOpts) { … }

// AST-based ObjC method rename, it renames all occurrences in the main file
// even for selectors which may have multiple tokens.
llvm::Expected<tooling::Replacements>
renameObjCMethodWithinFile(ParsedAST &AST, const ObjCMethodDecl *MD,
                           llvm::StringRef NewName,
                           std::vector<SourceLocation> SelectorOccurences) { … }

// AST-based rename, it renames all occurrences in the main file.
llvm::Expected<tooling::Replacements>
renameWithinFile(ParsedAST &AST, const NamedDecl &RenameDecl,
                 llvm::StringRef NewName) { … }

Range toRange(const SymbolLocation &L) { … }

// Walk down from a virtual method to overriding methods, we rename them as a
// group. Note that canonicalRenameDecl() ensures we're starting from the base
// method.
void insertTransitiveOverrides(SymbolID Base, llvm::DenseSet<SymbolID> &IDs,
                               const SymbolIndex &Index) { … }

// Return all rename occurrences (using the index) outside of the main file,
// grouped by the absolute file path.
llvm::Expected<llvm::StringMap<std::vector<Range>>>
findOccurrencesOutsideFile(const NamedDecl &RenameDecl,
                           llvm::StringRef MainFile, const SymbolIndex &Index,
                           size_t MaxLimitFiles) { … }

// Index-based rename, it renames all occurrences outside of the main file.
//
// The cross-file rename is purely based on the index, as we don't want to
// build all ASTs for affected files, which may cause a performance hit.
// We choose to trade off some correctness for performance and scalability.
//
// Clangd builds a dynamic index for all opened files on top of the static
// index of the whole codebase. Dynamic index is up-to-date (respects dirty
// buffers) as long as clangd finishes processing opened files, while static
// index (background index) is relatively stale. We choose the dirty buffers
// as the file content we rename on, and fallback to file content on disk if
// there is no dirty buffer.
llvm::Expected<FileEdits>
renameOutsideFile(const NamedDecl &RenameDecl, llvm::StringRef MainFilePath,
                  llvm::StringRef NewName, const SymbolIndex &Index,
                  size_t MaxLimitFiles, llvm::vfs::FileSystem &FS) { … }

// A simple edit is either changing line or column, but not both.
bool impliesSimpleEdit(const Position &LHS, const Position &RHS) { … }

// Performs a DFS to enumerate all possible near-miss matches.
// It finds the locations where the indexed occurrences are now spelled in
// Lexed occurrences, a near miss is defined as:
//   - a near miss maps all of the **name** occurrences from the index onto a
//     *subset* of lexed occurrences (we allow a single name refers to more
//     than one symbol)
//   - all indexed occurrences must be mapped, and Result must be distinct and
//     preserve order (only support detecting simple edits to ensure a
//     robust mapping)
//   - each indexed -> lexed occurrences mapping correspondence may change the
//     *line* or *column*, but not both (increases chance of a robust mapping)
void findNearMiss(
    std::vector<size_t> &PartialMatch, ArrayRef<Range> IndexedRest,
    ArrayRef<SymbolRange> LexedRest, int LexedIndex, int &Fuel,
    llvm::function_ref<void(const std::vector<size_t> &)> MatchedCB) { … }

} // namespace

SymbolRange::SymbolRange(Range R) : … { … }

SymbolRange::SymbolRange(std::vector<Range> Ranges)
    : … { … }

Range SymbolRange::range() const { … }

bool operator==(const SymbolRange &LHS, const SymbolRange &RHS) { … }
bool operator!=(const SymbolRange &LHS, const SymbolRange &RHS) { … }
bool operator<(const SymbolRange &LHS, const SymbolRange &RHS) { … }

llvm::Expected<RenameResult> rename(const RenameInputs &RInputs) { … }

llvm::Expected<Edit> buildRenameEdit(llvm::StringRef AbsFilePath,
                                     llvm::StringRef InitialCode,
                                     std::vector<SymbolRange> Occurrences,
                                     llvm::ArrayRef<llvm::StringRef> NewNames) { … }

// Details:
//  - lex the draft code to get all rename candidates, this yields a superset
//    of candidates.
//  - apply range patching heuristics to generate "authoritative" occurrences,
//    cases we consider:
//      (a) index returns a subset of candidates, we use the indexed results.
//        - fully equal, we are sure the index is up-to-date
//        - proper subset, index is correct in most cases? there may be false
//          positives (e.g. candidates got appended), but rename is still safe
//      (b) index returns non-candidate results, we attempt to map the indexed
//          ranges onto candidates in a plausible way (e.g. guess that lines
//          were inserted). If such a "near miss" is found, the rename is still
//          possible
std::optional<std::vector<SymbolRange>>
adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
                   std::vector<Range> Indexed, const LangOptions &LangOpts,
                   std::optional<Selector> Selector) { … }

std::optional<std::vector<SymbolRange>>
getMappedRanges(ArrayRef<Range> Indexed, ArrayRef<SymbolRange> Lexed) { … }

// The cost is the sum of the implied edit sizes between successive diffs, only
// simple edits are considered:
//   - insert/remove a line (change line offset)
//   - insert/remove a character on an existing line (change column offset)
//
// Example I, total result is 1 + 1 = 2.
//   diff[0]: line + 1 <- insert a line before edit 0.
//   diff[1]: line + 1
//   diff[2]: line + 1
//   diff[3]: line + 2 <- insert a line before edits 2 and 3.
//
// Example II, total result is 1 + 1 + 1 = 3.
//   diff[0]: line + 1  <- insert a line before edit 0.
//   diff[1]: column + 1 <- remove a line between edits 0 and 1, and insert a
//   character on edit 1.
size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed,
                                 ArrayRef<SymbolRange> Lexed,
                                 ArrayRef<size_t> MappedIndex) { … }

} // namespace clangd
} // namespace clang
llvm/clang-tools-extra/clangd/refactor/Rename.cpp
