[clangd] Reduce availability of extract function

[kadircet]

Summary

This patch introduces hoisting detection logic into prepare state with
a partial AST traversal of the enclosing function.

We had some complaints from the users about this code action being almost always
available but failing most of the time. Hopefully this should reduce that noise.

The latency/correctness tradeoff is a bunch of hand-waving, but at least today
we don't have any other actions that are available on selection of statements,
so when we get to do the traversal it is quite likely that all the other checks
will bail out early. But this is still up for discussion, I am happy to abandon
the patch if you believe this is not practical.

[sammccall]

clang-tools-extra/clangd/refactor/tweaks/ExtractFunction.cpp

321

Maybe obvious but "if any are, we can't perform extraction, as we don't support hoisting".

331

I think this would be clearer as two for loops:

• one filling RootStmts. i.e. the old generateRootStmts, though I do like inlining it here as it's initiaziling the ExtractionZone which really is this function's job
• the other looping over it as part of the big block of analysis that the comment applies to

As far as I can tell, the analysis doesn't have any side-effects, so I'd move it to a separate function (either a free function that you'd call here, or a member so the tweak can if (MaybeExtZone && MaybeExtZone->canApply()) or so. Again this is because mixing initialization and complex validation can make the data flow non-obvious.

Alternatively, maybe we can unify/reuse this logic? Surely it has a lot in common with captureZoneInfo() - is it really cheaper to run?

[kadircet]

• Address comments

[kadircet]

clang-tools-extra/clangd/refactor/tweaks/ExtractFunction.cpp

331

I think this would be clearer as two for loops:

done.

As far as I can tell, the analysis doesn't have any side-effects, so I'd move it to a separate function (either a free function that you'd call here, or a member so the tweak can if (MaybeExtZone && MaybeExtZone->canApply()) or so. Again this is because mixing initialization and complex validation can make the data flow non-obvious.

moved into a member named requiresHoisting.

Alternatively, maybe we can unify/reuse this logic? Surely it has a lot in common with captureZoneInfo() - is it really cheaper to run?

In theory this should be always cheaper than captureZoneInfo as it traverses the whole enclosing function, whereas this one only traverses ast nodes that intersect with selection or come after it.
So if selection is near the beginning of the function body, or the function itself is small, the delta is likely negligible.

clang-tools-extra/clangd/refactor/tweaks/ExtractFunction.cpp

 //    methods for rendering it.
 // 4. CapturedZoneInfo uses a RecursiveASTVisitor to capture information about
 //    the extraction like declarations, existing return statements, etc.
 // 5. getExtractedFunction is responsible for analyzing the CapturedZoneInfo and
 //    creating a NewFunction.
 //===----------------------------------------------------------------------===//
 
 #include "AST.h"
+#include "FindTarget.h"
 #include "ParsedAST.h"
 #include "Selection.h"
 #include "SourceCode.h"
 #include "refactor/Tweak.h"
 #include "support/Logger.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Stmt.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Refactoring/Extract/SourceExtraction.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace clangd {
struct ExtractionZone {
   // Parent of RootStatements being extracted.
   const Node *Parent = nullptr;
   // The half-open file range of the code being extracted.
   SourceRange ZoneRange;
   // The function inside which our zone resides.
   const FunctionDecl *EnclosingFunction = nullptr;
   // The half-open file range of the enclosing function.
   SourceRange EnclosingFuncRange;
+  // Set of statements that form the ExtractionZone.
+  llvm::DenseSet<const Stmt *> RootStmts;
+
   SourceLocation getInsertionPoint() const {
     return EnclosingFuncRange.getBegin();
   }
   bool isRootStmt(const Stmt *S) const;
   // The last root statement is important to decide where we need to insert a
   // semicolon after the extraction.
   const Node *getLastRootStmt() const { return Parent->Children.back(); }
-  void generateRootStmts();
 
-private:
-  llvm::DenseSet<const Stmt *> RootStmts;
+  // Checks if declarations inside extraction zone are accessed afterwards.
+  //
+  // This performs a partial AST traversal proportional to the size of the
+  // enclosing function, so it is possibly expensive.
+  bool requiresHoisting(const SourceManager &SM) const {
+    // First find all the declarations that happened inside extraction zone.
+    llvm::SmallSet<const Decl *, 1> DeclsInExtZone;
+    for (auto *RootStmt : RootStmts) {
+      findExplicitReferences(RootStmt,
+                             [&DeclsInExtZone](const ReferenceLoc &Loc) {
+                               if (!Loc.IsDecl)
+                                 return;
+                               DeclsInExtZone.insert(Loc.Targets.front());
+                             });
+    }
+    // Early exit without performing expensive traversal below.
+    if (DeclsInExtZone.empty())
+      return false;
+    // Then make sure they are not used outside the zone.
+    for (const auto *S : EnclosingFunction->getBody()->children()) {
+      if (SM.isBeforeInTranslationUnit(S->getSourceRange().getEnd(),
+                                       ZoneRange.getEnd()))
+        continue;
+      bool HasPostUse = false;
+      findExplicitReferences(S, [&](const ReferenceLoc &Loc) {
+        if (HasPostUse ||
+            SM.isBeforeInTranslationUnit(Loc.NameLoc, ZoneRange.getEnd()))
+          return;
+        HasPostUse =
+            llvm::any_of(Loc.Targets, [&DeclsInExtZone](const Decl *Target) {
+              return DeclsInExtZone.contains(Target);
+            });
+      });
+      if (HasPostUse)
+        return true;
+    }
+    return false;
+  }
 };
 
 // Whether the code in the extraction zone is guaranteed to return, assuming
 // no broken control flow (unbound break/continue).
 // This is a very naive check (does it end with a return stmt).
 // Doing some rudimentary control flow analysis would cover more cases.
 bool alwaysReturns(const ExtractionZone &EZ) {
   const Stmt *Last = EZ.getLastRootStmt()->ASTNode.get<Stmt>();
   // Unwrap enclosing (unconditional) compound statement.
   while (const auto *CS = llvm::dyn_cast<CompoundStmt>(Last)) {
     if (CS->body_empty())
       return false;
     else
       Last = CS->body_back();
   }
   return llvm::isa<ReturnStmt>(Last);
 }
 
 bool ExtractionZone::isRootStmt(const Stmt *S) const {
   return RootStmts.find(S) != RootStmts.end();
 }
 
-// Generate RootStmts set
-void ExtractionZone::generateRootStmts() {
-  for (const Node *Child : Parent->Children)
-    RootStmts.insert(Child->ASTNode.get<Stmt>());
-}
-
 // Finds the function in which the zone lies.
 const FunctionDecl *findEnclosingFunction(const Node *CommonAnc) {
   // Walk up the SelectionTree until we find a function Decl
   for (const Node *CurNode = CommonAnc; CurNode; CurNode = CurNode->Parent) {
     // Don't extract from lambdas
     if (CurNode->ASTNode.get<LambdaExpr>())
       return nullptr;
     if (const FunctionDecl *Func = CurNode->ASTNode.get<FunctionDecl>()) {
if (ExtZone.Parent->Children.size() == 1 &&
     return llvm::None;
   if (auto FuncRange =
           computeEnclosingFuncRange(ExtZone.EnclosingFunction, SM, LangOpts))
     ExtZone.EnclosingFuncRange = *FuncRange;
   if (auto ZoneRange = findZoneRange(ExtZone.Parent, SM, LangOpts))
     ExtZone.ZoneRange = *ZoneRange;
   if (ExtZone.EnclosingFuncRange.isInvalid() || ExtZone.ZoneRange.isInvalid())
     return llvm::None;
-  ExtZone.generateRootStmts();
+
+  for (const Node *Child : ExtZone.Parent->Children)
+    ExtZone.RootStmts.insert(Child->ASTNode.get<Stmt>());
+
   return ExtZone;
 }
 
 // Stores information about the extracted function and provides methods for
 // rendering it.
 struct NewFunction {
   struct Parameter {
     std::string Name;
     QualType TypeInfo;
     bool PassByReference;
     unsigned OrderPriority; // Lower value parameters are preferred first.
     std::string render(const DeclContext *Context) const;
     bool operator<(const Parameter &Other) const {
       return OrderPriority < Other.OrderPriority;
     }
   };

 
 tooling::Replacement createFunctionDefinition(const NewFunction &ExtractedFunc,
                                               const SourceManager &SM) {
   std::string FunctionDef = ExtractedFunc.renderDefinition(SM);
   return tooling::Replacement(SM, ExtractedFunc.InsertionPoint, 0, FunctionDef);
 }
 
 bool ExtractFunction::prepare(const Selection &Inputs) {
-  const Node *CommonAnc = Inputs.ASTSelection.commonAncestor();
-  const SourceManager &SM = Inputs.AST->getSourceManager();
   const LangOptions &LangOpts = Inputs.AST->getLangOpts();
   if (!LangOpts.CPlusPlus)
     return false;
-  if (auto MaybeExtZone = findExtractionZone(CommonAnc, SM, LangOpts)) {
-    ExtZone = std::move(*MaybeExtZone);
-    return true;
-  }
-  return false;
-}
+  const Node *CommonAnc = Inputs.ASTSelection.commonAncestor();
+  const SourceManager &SM = Inputs.AST->getSourceManager();
+  auto MaybeExtZone = findExtractionZone(CommonAnc, SM, LangOpts);
+  // FIXME: Get rid of this check once we support hoisting.
+  if (!MaybeExtZone || MaybeExtZone->requiresHoisting(SM))
+    return false;
+
 
 Expected<Tweak::Effect> ExtractFunction::apply(const Selection &Inputs) {
   const SourceManager &SM = Inputs.AST->getSourceManager();
   const LangOptions &LangOpts = Inputs.AST->getLangOpts();
   auto ExtractedFunc = getExtractedFunction(ExtZone, SM, LangOpts);
   // FIXME: Add more types of errors.
   if (!ExtractedFunc)
     return ExtractedFunc.takeError();

clang-tools-extra/clangd/unittests/TweakTests.cpp

TEST_F(ExtractFunctionTest, FunctionTest) {
   // Root statements should have common parent.
   EXPECT_EQ(apply("for(;;) [[1+2; 1+2;]]"), "unavailable");
   // Expressions aren't extracted.
   EXPECT_EQ(apply("int x = 0; [[x++;]]"), "unavailable");
   // We don't support extraction from lambdas.
   EXPECT_EQ(apply("auto lam = [](){ [[int x;]] }; "), "unavailable");
   // Partial statements aren't extracted.
   EXPECT_THAT(apply("int [[x = 0]];"), "unavailable");
+  // FIXME: Support hoisting.
+  EXPECT_THAT(apply(" [[int a = 5;]] a++; "), "unavailable");
 
   // Ensure that end of Zone and Beginning of PostZone being adjacent doesn't
   // lead to break being included in the extraction zone.
   EXPECT_THAT(apply("for(;;) { [[int x;]]break; }"), HasSubstr("extracted"));
   // FIXME: ExtractFunction should be unavailable inside loop construct
   // initializer/condition.
   EXPECT_THAT(apply(" for([[int i = 0;]];);"), HasSubstr("extracted"));
-  // Don't extract because needs hoisting.
-  EXPECT_THAT(apply(" [[int a = 5;]] a++; "), StartsWith("fail"));
   // Extract certain return
   EXPECT_THAT(apply(" if(true) [[{ return; }]] "), HasSubstr("extracted"));
   // Don't extract uncertain return
   EXPECT_THAT(apply(" if(true) [[if (false) return;]] "), StartsWith("fail"));
 
   FileName = "a.c";
   EXPECT_THAT(apply(" for([[int i = 0;]];);"), HasSubstr("unavailable"));
 }