[Clangd] First version of ExtractFunction

[SureYeaah]

Summary

• Only works for extraction from free functions
• Basic analysis of the code being extracted.
• Extract to void function
• Bail out if extracting a return, continue or break.
• Doesn't hoist decls yet

[sammccall]

I guess you're looking for design review at this point.

But the most important part of that is the documentation of the high-level structure, which is entirely missing. I can't really infer it from the code because most of the design is (presumably) not implemented at this point :-)

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

37

I think "range" or "region" may be a clearer name here than "target".
(In extract variable, target was used to refer to the destination of extraction)

111

what is the fix you're waiting for?

156

These are important domain structures, can we move them out of the RecursiveASTVisitor? (which should be mostly restricted to managing state of the traversal itself)

157

You've called this "reference", but I think it's actually a "referenceddecl" - you don't store one of these for each reference do you?

190

why does D need to be a vardecl?

191

please don't add messages to asserts that just echo the code. In order of preference:

• take a reference so it clearly can't be null
• add a message explaining at a *high level* what variant is violated
• add the assertion with no message

198

why is this handled specially, instead of being part of the general case of "referring to a decl not visible in the target scope"?

(in particular, if the context is forward-declared elsewhere, what's the problem?

204

DRE is just one of the cases where we want to handle names.

I think it'll be easier to handle more cases by changing this to accept a Decl* and moving the DRE->getDecl() to the caller

208

(why beginloc rather than loc, throughout?)

212

this line seems very suspect, what are you trying to do and why?

215

can't we skip the indirection here and just have something like Ref.markOccurrence(DRE->getBeginLoc()), and avoid dealing with the enum here at all?

[SureYeaah]

In D65526#1612117, @sammccall wrote:

I guess you're looking for design review at this point.

But the most important part of that is the documentation of the high-level structure, which is entirely missing. I can't really infer it from the code because most of the design is (presumably) not implemented at this point :-)

Aaah. Yes. Sorry. Makes sense.

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

111

The semicolon fix that has already landed now.

212

This just checks whether (DeclLocType, DRELocType) is either (PRETARGET, TARGET) or (TARGET, POSTTARGET). Could explicitly write it if needed.

[sammccall]

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

212

Definitely needed, apart from the lack of clarity the current version has UB sometimes (DeclLocType + 1 might not be a valid value)

But by "why" i mostly mean - this looks like the place for recording the location, not the place for deciding not to record the location because some algorithm later may not need it. Seems a lot simpler to record it unconditionally and worry about it later.

[SureYeaah]

Refactored design and added unit tests.

[SureYeaah]

Removed unrelated changes

[SureYeaah]

Removed debug info

[SureYeaah]

Better Naming

[SureYeaah]

Fixed bug in getLocType

[SureYeaah]

Fixed semicolon bug

[kadircet]

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

69

Could you move the definition of RootStmt to class definition? Since it is used in a lot more places than just this one.

69

We only support extraction of RootStmts.

Can you also mention the reasoning/implications ?

72

Can you make this and the computeEnclosingFunction{,Rng} free functions instead of static methods?

75

haven't checked the implementation yet, but naming and the comments seem to be ambiguous.

Do you mean *selected* childrens of Parent, instead of *all*? Because IIUC, Source refers to the part of the function body that is selected, not all of it, right?

223

comments for some of the fields like SemicolonPolicy would be nice.

also most of these looks like implementation details, consider moving internal ones to private

287

could you give more details on what is collected and how?

361

why not move this and 4 following functions into astvisitor?

[sammccall]

Main themes are:

• there are a few places we can reduce scope for the first patch: e.g. template support
• internally, it'd be clearer to pass data around in structs and avoid complex classes unless the abstraction is important
• high-level documentation would aid in understanding: for each concept/function: what is the goal, how does it fit into higher-level goals, are there any non-obvious reasons it's done this way
• naming questions (this can solve some of the same problems as docs, but much more cheaply)

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

8

this file will need an overview describing

• the refactoring, and (briefly) major user-visible design decisions (e.g. params, return types, hoisting)
• structure/approach/major parts

38

this name is *also* pretty confusing because of SourceLocation, SourceRange etc classes.

Best option might just be to make up something distinctive, like Zone :-/

40

nit: if you're going to document the values one-by-one, do it in a comment on each value instead

43

nit: we don't use MACROCASE for enums in LLVM (I think). This of course makes namespacing more important, we should consider enum class here.

I'd probably suggest

enum class ZoneRelative { // or some name consistent with above
  Before,
  After,
  Inside,
  External
};

46

This looks like basically a struct (mostly public data members) where all the logic is in the constructor.
This would be more obvious/more consistent with style elsewhere if it were literally a struct and the constructor was instead a function (which could return Expected<ExtractionSourceView> instead of setting flags on the result)

46

nit: not sure view adds anything here. ExtractionSource or ExtractionZone?

51

classify?

60

when is this not Parent->Children.back()?

94

I think you probably want to avoid extracting from lambdas and templates for now, too.

105

nit: Please spell 'range' rather than 'rng' in function names, as it's not a standard abbreviation in clang[d]

108

can we avoid adding template support in the first patch? It's complicated, and I don't think the code below handles it robustly.

For instance, this case will be extracted (despite being dependent), because the reference to T is not seen by the ast visitor, and the type of the decls that are seen are not dependent:

template <typename T>
int zero() { return std::vector<T>().size(); }

114

It's not clear what this function does and why. Can you add a high-level comment?

125

LLVM_FALLTHROUGH

(we support other host compilers: msvc, gcc)

145

what needs to be fixed, and why is it important?

176

what is this function doing, and why?
why is it separated from getParentOfRootStmts?

it seems like we're trying to determine that the selection consists of either a single completely-selected stmt, or a bunch of completely-selected statements with a common parent, and then we represent them as "all the children of a certain parent node".

Splitting the logic into two distant functions, and not documenting this intent, makes it hard to follow.

207

as above, this seems like it would be clearer as a struct.

215

I'd suggest capturing the type as a QualType instead of a string + const + ref flag

When types may need to be re-spelled, we'll need that extra information - the context needed to re-spell is available at render() time, not addParameter() time.

226

We tend to avoid std::set except in the rare cases where we need both sorting and on-the-fly deduplication.

Here, it seems std::vector would be enough, and explicitly sorting an the end would make the intent clearer.

227

Hoisting isn't supported, drop this?

236

as previously discussed, there's not enough (conceptual or implementation) commonality between the call and the declaration, can we have separate renderDefinition() and renderCall() functions?

263

these TODOs don't really describe the structural change that's needed here: we need a way to apply a bunch of edits to the function text (in terms of the original coordinates).

401

I'm confused about the decls to host part - this isn't actually supported right? Take it out of the name?

Or are they detected in order to cause the refactoring to fail?

455

you've got a return type, a comment, and a function name, and they all say the same thing. Can you explain (at a high level) what this is for?

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

603

the test helpers are really aimed at testing prepare/apply together rather than separately.

These EXPECT_AVAILABLE could be EXPECT_EQ(apply(), ...). If prepare() returns false it'll return "prepare failed" or some string like that.

618

rather than checking in commented-out tests, I'd prefer to check in the tests verifying current incorrect behavior with a FIXME.
Commented out code tends to rot (or often not quite work in the first place), and it's not discoverable

(or just leave the FIXME by itself)

639

maybe add a comment saying why not?

649

this line does nothing?

651

IIRC you can't use raw strings inside a macro (it's legal, but one of the supported compilers chokes on it)

654

please avoid large tests that test lots of things, test them one-at-a-time instead. The intent is clearer, and it's clearer what failures mean.

683

please write these out explicitly instead.
Among other things, the goal in the helpers was that assertion failures should preserve line numbers of examples

[SureYeaah]

Addressed Review comments

[SureYeaah]

Addressed more review comments

[SureYeaah]

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

215

Const will also depend on CapturedSourceInfo. So I'm passing QualType instead of the name as string.

361

Because we would need to pass CapturedSourceInfo and ExtractionZone to the Visitor then?

[SureYeaah]

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

361

Ignore.

[SureYeaah]

Removed extra code

[SureYeaah]

Fixed typo

[kadircet]

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

30

did you mean no return *type* ?

31

don't understand what you meant here

32

could you elaborate on that one?

You can ignore this comment if it is gonna be explained in the design doc(and you are planning to attach it before landing this revision)

43

Tried hard to figure out what RAV is :D could you rather say RecursiveASTVisitor(RAV) ?

123

IIRC, < operator in SourceLocations are merely for implementing hashing and doesn't really carry less than semantics. Could you rather use SM.isBeforeInSLocAddrSpace?

125

same here

134

Can you rather return a FunctionDecl ?

153

maybe rather return an llvm::Optional/Expected ?

166

I suppose this relies on the fact that "AST contains the nodes ordered by their begin location"? Could you add an assertion for that?

177

what makes this fail-free ?

181

This explains *what* the function is doing, but lacks the *reason why*

Could you explain the reason either in here or in the call site?

182

hasOnlyRootStmtsAsChildren ?

216

why ?

226

why is this function returning a shared_ptr ?

333

why don't we infer this const from QualType ?

348

what does numbering mean ?

481

nit: move this to top of the loop

520

maybe return an llvm::Expected so that we can tell user about the reason why refactoring failed?

548

why do you need a shared_ptr here?

[sammccall]

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

47

please fix or remove comment

89

nit: "wrt to" -> wrt

105

remove from struct and pass as a parameter?
This isn't really data

113

document why this is important, or just inline it?

114

don't bother handling the null parent case. When can that happen? We should avoid creating an ExtractionZone struct entirely then.

Also none of the callsites bother to check for null...

133

nit: consistently one blank line between functions (in this file you alternate between 1/0)

158

why are you doing this with a loop, isn't it just {first->begin,last->end}?

182

nit: I think this would be clearer as
canBeRootStmt(const Node*) and write the callsite as llvm::any_of(CommonAnc->Children, canBeRootStmt). Up to you though

226

avoid shared_ptr unless there's a strong reason. Optional<ExtractionZone> seems fine here?

258

there's no need for the WithTypeAndQualifiers=false version, that's just "fn.name"

271

this is just initializing public fields, drop the constructor?
(The callsite is clearer here if you initialize them by name)

281

this is just push_back, inline into caller

286

again, avoid sharing code between the complicated declaration case, and the trivial callsite case. It makes changes harder and obscures the hard case.

327

use printType from AST.h?

(You'll want to drop qualifiers/refs before calling that, but it's not at all obvious from the function name here that they're dropped, so that should be at the callsite anyway)

347

missing initializers on this and DeclIndex

348

Giving a definition of "index" isn't useful here :-)
Rather prefer to say what it's the index of: is it the index of first reference, relative to the other decls?

353

what is this constructor for?

376

Again, the comment just echoes the code. There is some subtlety here, either explain it ("the index is the size of the map so far, so it increases for each decl found") or ignore it - this isn't too hard to work out.

411

please don't add these NOLINT comments everywhere. It's too noisy and we don't do it elsewhere (agree we should silence clang-tidy somehow)

431

computing and checking bounds for every node in the same function seems unneccesarily inefficient.

Why not override TraverseStmt to set a flag to true when the stmt is a RootStmt, call Base::TraverseStmt then set it to false again after?

456

seems you could write this more directly - e.g. it's natural to check for hoisting here.

if (DeclaredIn == Inside && ReferencedInPostZone)
  return false; // needs to be hoisted, not supported
if (!ReferencedInZone)
  continue; // no need to pass as parameter, not referenced
if (DeclaredIn == Inside || DeclaredIn == OutsideFunc)
  continue; // no need to pass as parameter, still accessible

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

611

wait, what?
expressions that *aren't statements* shouldn't be extracted.
But what's wrong with this one?
(Many useful statements are expressions, such as function calls)

615

please clarify this comment (specifically what needs to be fixed?) ideally add the broken test case with a FIXME to fix it

621

add a more realistic example? I can easily imagine banning this case in the future (extraction of an empty block)

641

please make the tests use reasonably conventional style - FOO -> Foo, one statement per line, etc

[SureYeaah]

Addressed review comments

[SureYeaah]

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

166

I've removed the loop, should I still add this?

182

Replaced with isRootStmt

226

And store a unique_ptr to the optional in ExtractFunction?

226

Because ExtractFunction needs to store a pointer/reference to ExtractionZone somehow in prepare and access it in apply.

271

ExtractionSemicolonPolicy doesn't have a default constructor.

333

In a future patch we will want to use heuristics like has the variable been assigned, was it passed as a non-const reference, was its address taken, etc.

548

getExtractionZone creates an Optional<ExtractionZone> which needs to persist from prepare to apply. Is there a better way to store a reference to the ExtractionZone instance inside ExtractFunction?

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

611

For now we don't extract if the selection is an expression. I've added a fixme to change that to sub-expressions only.

[SureYeaah]

NFC: Whitespace formatting

[sammccall]

I think we should go ahead and land this. The only points that I'd really like to see fixed is shared_ptr, mostly because it's a strong signal there's something complicated going on and I don't think (or hope) there is!

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

120

D66872 has the fix if you'd rather avoid these workarounds

147

llvm::DenseSet<const Stmt*>

std::set is a pretty terrible data structure unless you really really need order.
(Lots of allocations, lots of pointer-chasing)

239

this is also:

for (const SelectionTree::Node *N)
  ExtZone->RootStmts.insert(N->ASTNode.get<Stmt>());

which is shorter and (I think) less obfuscated

327

Second half is not done: the suggestion is that it's really confusing where spellType is called that it drops qualifiers, so just I'd inline this into the callsite.

333

I think the point is that the QualType in parameter could/should represent the *parameter* type, not the type of the variable being captured.
e.g. it could be const std::string& even if the original variable was just std::string.

This seems the more natural model (the struct is called Parameter, not CapturedVariable or Argument) but there may be reasons not to do this.

548

shared ownership is less common and harder to reason about than exclusive ownership

Generally we prefer deciding where ownership should reside (T or Optional<T> or unique_ptr<T>), and where you should have an unowned reference (T& or T*).

In this case, findExtractionZone() should ideally return Optional<ExtractionZone>, after prepare() the ExtractFunction class should own it (as a Optional<ExtractionZone>), and apply should pass it around as a const ExtractionZone&.

If it turns out ExtractionZone isn't a movable type, then Optional<ExtractionZone> won't work and you'll need unique_ptr<ExtractionZone> instead. But shared_ptr shouldn't be needed regardless.

[kadircet]

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

147

lifetime of this field looks complicated can you add some comments on how/when it is initialized and maybe enforce immutability ?

151

it seems like you are rather using it to decide whether a statement is inside the zone or not?

Could you rather rename it to reflect that and add some comments?

166

no need

170

nit:

if (isa<CXXMethodDecl>(Func))

173

nit:

if(isa<FunctionTemplateDecl>(Func))

226

Let's figure it out in the ExtractFunction this can still return an Optional<ExtractionZone> which you can convert into a pointer/reference later on if need be?

347

i think you mean index of the first reference to this decl ?

487

nit isa<FunctionDecl> instead of dyn_cast

548

Then why not just store Optional<ExtractionZone> ?

[SureYeaah]

Addressed review comments

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

120

Will remove this once D66872 is committed.

151

if extracting

for(;;)
  int x = 0;

the DeclStmt is inside the zone but not a rootstmt.

173

Using Func->isTemplated()

347

It can be the index of declaration or the first reference. Since the visitor Visits Decls as well, we will encounter a reference before the Decl only if the Decl is outside the enclosing function.

clang-tools-extra/clangd/refactor/tweaks/CMakeLists.txt

 # To enable these tweaks in executables or shared libraries, add
 # $<TARGET_OBJECTS:obj.clangDaemonTweaks> to a list of sources, see
 # clangd/tool/CMakeLists.txt for an example.
 add_clang_library(clangDaemonTweaks OBJECT
   AnnotateHighlightings.cpp
   DumpAST.cpp
   ExpandAutoType.cpp
   ExpandMacro.cpp
+  ExtractFunction.cpp
   ExtractVariable.cpp
   RawStringLiteral.cpp
   SwapIfBranches.cpp
 
   LINK_LIBS
   clangAST
   clangBasic
   clangDaemon
   clangToolingCore
   clangToolingSyntax
   )

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

+//===--- ExtractFunction.cpp -------------------------------------*- 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 "ClangdUnit.h"
+#include "Logger.h"
+#include "Selection.h"
+#include "SourceCode.h"
+#include "refactor/Tweak.h"
+#include "clang/AST/ASTContext.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/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 {
+namespace {
+
+using Node = SelectionTree::Node;
+
+// ExtractionZone is the part of code that is being extracted.
+// EnclosingFunction is the function/method inside which the source lies.
+// We split the file into 4 parts relative to extraction zone.
+enum class ZoneRelative {
+  Before,     // Before Zone and inside EnclosingFunction.
+  Inside,     // Inside Zone.
+  After,      // After Zone and inside EnclosingFunction.
+  OutsideFunc // Outside EnclosingFunction.
+};
+
+// The ExtractionZone class forms a view of the code wrt to Zone.
+// A RootStmt is a statement that's fully selected including all it's children
+// and it's parent is unselected.
+// We only support extraction of RootStmts since it allows us to extract without
+// having to change the selection range. Also, this means that any scope that
+// begins in selection range, ends in selection range and any scope that begins
+// outside the selection range, ends outside as well.
+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 source resides.
+  const Node *EnclosingFunction = nullptr;
+  // The half-open file range of the enclosing function.
+  SourceRange EnclosingFuncRange;
+  const SourceManager &SM;
+
+  ExtractionZone(const SourceManager &SM) : SM(SM){};
+  // Classify the location type for a given location.
+  ZoneRelative getRelationToZone(SourceLocation Loc) const;
+  SourceLocation getInsertionPoint() const {
+    return EnclosingFuncRange.getBegin();
+  }
+  const Node *getLastRootStmt() const {
+    return Parent ? Parent->Children.back() : nullptr;
+  }
+};
+
+// TODO: check if this works properly with macros.
+ZoneRelative ExtractionZone::getRelationToZone(SourceLocation Loc) const {
+  if (!SM.isPointWithin(Loc, EnclosingFuncRange.getBegin(),
+                        EnclosingFuncRange.getEnd()))
+    return ZoneRelative::OutsideFunc;
+  if (Loc < ZoneRange.getBegin())
+    return ZoneRelative::Before;
+  if (Loc < ZoneRange.getEnd())
+    return ZoneRelative::Inside;
+  return ZoneRelative::After;
+}
+
+// Finds the function in which the source lies.
+const Node *computeEnclosingFunction(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 (CurNode->ASTNode.get<FunctionDecl>()) {
+      // FIXME: Support extraction from methods.
+      if (CurNode->ASTNode.get<CXXMethodDecl>())
+        return nullptr;
+      // FIXME: Support extraction from templated functions.
+      if (CurNode->Parent->ASTNode.get<FunctionTemplateDecl>())
+        return nullptr;
+      return CurNode;
+    }
+  }
+  return nullptr;
+}
+
+// Find the union of source ranges of all child nodes of Parent. Returns an
+// invalid SourceRange if it fails to do so.
+SourceRange rangeUnionOfChildren(const Node *Parent, const SourceManager &SM,
+                                 const LangOptions &LangOpts) {
+  SourceRange SR;
+  for (const Node *Child : Parent->Children) {
+    auto ChildFileRange =
+        toHalfOpenFileRange(SM, LangOpts, Child->ASTNode.getSourceRange());
+    if (!ChildFileRange)
+      return SourceRange();
+    if (SR.isInvalid())
+      SR = *ChildFileRange;
+    else
+      SR.setEnd(ChildFileRange->getEnd());
+  }
+  return SR;
+}
+// Compute the range spanned by the enclosing function.
+// FIXME: check if EnclosingFunction has any attributes as the AST doesn't
+// always store the source range of the attributes and thus we end up extracting
+// between the attributes and the EnclosingFunction.
+SourceRange computeEnclosingFuncRange(const Node *EnclosingFunction,
+                                      const SourceManager &SM,
+                                      const LangOptions &LangOpts) {
+  return *toHalfOpenFileRange(SM, LangOpts,
+                              EnclosingFunction->ASTNode.getSourceRange());
+}
+
+// Check if all child nodes of (unselected) Parent are RootStmts.
+bool hasOnlyRootStmtChildren(const Node *Parent) {
+  for (const Node *Child : Parent->Children) {
+    // Ensure every child is a statement.
+    if (!Child->ASTNode.get<Stmt>())
+      return false;
+    // We don't want to extract a partially selected subtree.
+    if (Child->Selected == SelectionTree::Partial)
+      return false;
+    // Only DeclStmt can be an unselected child since VarDecls claim the entire
+    // selection range in selectionTree.
+    if (Child->Selected == SelectionTree::Selection::Unselected &&
+        !Child->ASTNode.get<DeclStmt>())
+      return false;
+  }
+  return true;
+}
+
+// Returns the (unselected) parent of all RootStmts given the commonAncestor.
+const Node *getParentOfRootStmts(const Node *CommonAnc) {
+  if (!CommonAnc)
+    return nullptr;
+  switch (CommonAnc->Selected) {
+  case SelectionTree::Selection::Unselected:
+    return hasOnlyRootStmtChildren(CommonAnc) ? CommonAnc : nullptr;
+  case SelectionTree::Selection::Partial:
+    // Treat Partially selected VarDecl as completely selected since
+    // SelectionTree doesn't always select VarDecls correctly.
+    if (!CommonAnc->ASTNode.get<VarDecl>())
+      return nullptr;
+    LLVM_FALLTHROUGH;
+  case SelectionTree::Selection::Complete:
+    // If the Common Ancestor is completely selected, then it's a root statement
+    // and its parent will be unselected.
+    const Node *Parent = CommonAnc->Parent;
+    // If parent is a DeclStmt, even though it's unselected, we consider it a
+    // root statement and return its parent.
+    return Parent->ASTNode.get<DeclStmt>() ? Parent->Parent : Parent;
+  }
+}
+
+// FIXME: Check we're not extracting from the initializer/condition of a control
+// flow structure.
+// FIXME: Check that we don't extract the compound statement of the
+// enclosingFunction.
+std::shared_ptr<ExtractionZone> getExtractionZone(const Node *CommonAnc,
+                                                  const SourceManager &SM,
+                                                  const LangOptions &LangOpts) {
+  std::shared_ptr<ExtractionZone> ExtZone =
+      std::make_shared<ExtractionZone>(SM);
+  ExtZone->Parent = getParentOfRootStmts(CommonAnc);
+  if (!ExtZone->Parent || ExtZone->Parent->Children.empty())
+    return nullptr;
+  ExtZone->EnclosingFunction = computeEnclosingFunction(ExtZone->Parent);
+  if (!ExtZone->EnclosingFunction)
+    return nullptr;
+  ExtZone->EnclosingFuncRange =
+      computeEnclosingFuncRange(ExtZone->EnclosingFunction, SM, LangOpts);
+  // Don't extract expressions.
+  if (ExtZone->Parent->Children.size() == 1 &&
+      ExtZone->getLastRootStmt()->ASTNode.get<Expr>())
+    return nullptr;
+  // Since all children of Parent are RootStmts, ZoneRange will be union of
+  // SourceRange of all it's children.
+  ExtZone->ZoneRange = rangeUnionOfChildren(ExtZone->Parent, SM, LangOpts);
+  return ExtZone;
+}
+
+// Stores information about the extracted function and provides methods for
+// rendering it.
+struct NewFunction {
+  struct Parameter {
+    std::string Name;
+    std::string Type;
+    bool IsConst;
+    // Lower value parameters are preferred first.
+    unsigned OrderPriority;
+    bool PassByReference = true;
+    Parameter(std::string Name, std::string Type, bool IsConst,
+              unsigned OrderPriority)
+        : Name(Name), Type(Type), IsConst(IsConst),
+          OrderPriority(OrderPriority) {}
+    std::string render(bool WithTypeAndQualifiers) const;
+    bool operator<(const Parameter &Other) const {
+      return OrderPriority < Other.OrderPriority;
+    }
+  };
+  std::string Name = "extracted";
+  std::string ReturnType;
+  std::vector<Parameter> Parameters;
+  SourceRange BodyRange;
+  SourceLocation InsertionPoint;
+  // Decides whether the extracted function body and the function call need a
+  // semicolon after extraction.
+  tooling::ExtractionSemicolonPolicy SemicolonPolicy;
+  NewFunction(SourceRange BodyRange, SourceLocation InsertionPoint,
+              tooling::ExtractionSemicolonPolicy SemicolonPolicy,
+              const SourceManager &SM)
+      : BodyRange(BodyRange), InsertionPoint(InsertionPoint),
+        SemicolonPolicy(SemicolonPolicy), SM(SM){};
+  // Render the call for this function.
+  std::string renderCall() const;
+  // Render the definition for this function.
+  std::string renderDefinition() const;
+  // Add a new parameter for the function.
+  void addParam(llvm::StringRef Name, llvm::StringRef Type, bool IsConst,
+                unsigned OrderPriority);
+
+private:
+  const SourceManager &SM;
+  std::string renderParameters(bool WithTypeAndQualifiers) const;
+  // Generate the function body.
+  std::string getFuncBody() const;
+};
+
+std::string NewFunction::renderParameters(bool WithTypeAndQualifiers) const {
+  std::string Result;
+  bool NeedCommaBefore = false;
+  for (const Parameter &P : Parameters) {
+    if (NeedCommaBefore)
+      Result += ", ";
+    NeedCommaBefore = true;
+    Result += P.render(WithTypeAndQualifiers);
+  }
+  return Result;
+}
+std::string NewFunction::renderCall() const {
+  return Name + "(" + renderParameters(false) + ")" +
+         (SemicolonPolicy.isNeededInOriginalFunction() ? ";" : "");
+}
+std::string NewFunction::renderDefinition() const {
+  return ReturnType + " " + Name + "(" + renderParameters(true) + ")" + " {\n" +
+         getFuncBody() + "\n}\n";
+}
+
+std::string NewFunction::getFuncBody() const {
+  // FIXME: Generate tooling::Replacements instead of std::string to
+  // - hoist decls
+  // - add return statement
+  // - Add semicolon
+  return toSourceCode(SM, BodyRange).str() +
+         (SemicolonPolicy.isNeededInExtractedFunction() ? ";" : "");
+}
+
+void NewFunction::addParam(llvm::StringRef Name, llvm::StringRef Type,
+                           bool IsConst, unsigned OrderingPriority) {
+  Parameters.push_back(Parameter(Name, Type, IsConst, OrderingPriority));
+}
+
+std::string NewFunction::Parameter::render(bool WithTypeAndQualifiers) const {
+  std::string Result;
+  if (WithTypeAndQualifiers) {
+    if (IsConst)
+      Result += "const ";
+    Result += Type + " ";
+    if (PassByReference)
+      Result += "&";
+  }
+  Result += Name;
+  return Result;
+}
+
+// Captures information about the source.
+class CapturedSourceInfo {
+public:
+  struct DeclInformation {
+    const Decl *TheDecl = nullptr;
+    ZoneRelative DeclaredIn;
+    unsigned DeclarationIndex;
+    bool IsReferencedInSource = false;
+    bool IsReferencedInPostSource = false;
+    bool IsAssigned = false;
+    bool MaybeModifiedOutside = false;
+    DeclInformation(){};
+    DeclInformation(const Decl *TheDecl, ZoneRelative DeclaredIn,
+                    unsigned DeclarationIndex)
+        : TheDecl(TheDecl), DeclaredIn(DeclaredIn),
+          DeclarationIndex(DeclarationIndex){};
+    void markOccurence(ZoneRelative ReferenceLoc);
+  };
+  llvm::DenseMap<const Decl *, DeclInformation> DeclInfoMap;
+  bool HasReturnStmt = false;
+  // For now we just care whether there exists a break/continue or not.
+  bool HasBreakOrContinue = false;
+  // FIXME: capture TypeAliasDecl and UsingDirectiveDecl
+  // FIXME: Capture type information as well.
+private:
+  // Return reference for a Decl, adding it if not already present.
+  DeclInformation &getDeclInformationFor(const Decl *D);
+  const ExtractionZone &ExtZone;
+  CapturedSourceInfo(const ExtractionZone &ExtZone) : ExtZone(ExtZone) {}
+
+public:
+  static CapturedSourceInfo captureInfo(const ExtractionZone &ExtZone);
+  void captureBreakOrContinue(const Stmt *BreakOrContinue);
+  void captureReturn(const Stmt *Return);
+  void captureReference(const DeclRefExpr *DRE);
+};
+
+CapturedSourceInfo
+CapturedSourceInfo::captureInfo(const ExtractionZone &ExtZone) {
+  // We use the ASTVisitor instead of using the selection tree since we need to
+  // find references in the PostSource as well.
+  // FIXME: Check which statements we don't allow to extract.
+  class ExtractionZoneVisitor
+      : public clang::RecursiveASTVisitor<ExtractionZoneVisitor> {
+  public:
+    ExtractionZoneVisitor(CapturedSourceInfo &Info) : Info(Info) {}
+    bool VisitDecl(Decl *D) { // NOLINT
+      Info.getDeclInformationFor(D);
+      return true;
+    }
+    bool VisitDeclRefExpr(DeclRefExpr *DRE) { // NOLINT
+      Info.captureReference(DRE);
+      return true;
+    }
+    bool VisitReturnStmt(ReturnStmt *Return) { // NOLINT
+      Info.captureReturn(Return);
+      return true;
+    }
+    bool VisitBreakStmt(BreakStmt *Break) { // NOLINT
+      Info.captureBreakOrContinue(Break);
+      return true;
+    }
+    bool VisitContinueStmt(ContinueStmt *Continue) { // NOLINT
+      Info.captureBreakOrContinue(Continue);
+      return true;
+    }
+
+  private:
+    CapturedSourceInfo &Info;
+  };
+  CapturedSourceInfo Info(ExtZone);
+  ExtractionZoneVisitor Visitor(Info);
+  Visitor.TraverseDecl(const_cast<FunctionDecl *>(
+      ExtZone.EnclosingFunction->ASTNode.get<FunctionDecl>()));
+  return Info;
+}
+
+CapturedSourceInfo::DeclInformation &
+CapturedSourceInfo::getDeclInformationFor(const Decl *D) {
+  // Adding a new Decl (The declarationIndex will be the size of the
+  // DeclInfoMap).
+  if (DeclInfoMap.find(D) == DeclInfoMap.end())
+    DeclInfoMap.insert(
+        {D, DeclInformation(D, ExtZone.getRelationToZone(D->getLocation()),
+                            DeclInfoMap.size())});
+  return DeclInfoMap[D];
+}
+
+// FIXME: check if reference mutates the Decl being referred.
+void CapturedSourceInfo::captureReference(const DeclRefExpr *DRE) {
+  DeclInformation &DeclInfo = getDeclInformationFor(DRE->getDecl());
+  DeclInfo.markOccurence(ExtZone.getRelationToZone(DRE->getLocation()));
+}
+
+void CapturedSourceInfo::captureReturn(const Stmt *Return) {
+  if (ExtZone.getRelationToZone(Return->getBeginLoc()) == ZoneRelative::Inside)
+    HasReturnStmt = true;
+}
+
+// FIXME: check for broken break/continue only.
+void CapturedSourceInfo::captureBreakOrContinue(const Stmt *BreakOrContinue) {
+  if (ExtZone.getRelationToZone(BreakOrContinue->getBeginLoc()) ==
+      ZoneRelative::Inside)
+    HasBreakOrContinue = true;
+}
+
+void CapturedSourceInfo::DeclInformation::markOccurence(
+    ZoneRelative ReferenceLoc) {
+  switch (ReferenceLoc) {
+  case ZoneRelative::Inside:
+    IsReferencedInSource = true;
+    break;
+  case ZoneRelative::After:
+    IsReferencedInPostSource = true;
+    break;
+  default:
+    break;
+  }
+}
+
+// Adds parameters to ExtractedFunc.
+// Returns true if able to find the parameters successfully and no hoisting
+// needed.
+bool createParameters(NewFunction &ExtractedFunc,
+                      const CapturedSourceInfo &CapturedInfo) {
+  // FIXME: Generate better types names. e.g. remove class from object types.
+  auto GetDeclType = [](const ValueDecl *D) {
+    return D->getType()
+        .getUnqualifiedType()
+        .getNonReferenceType()
+        .getAsString();
+  };
+
+  for (const auto &KeyVal : CapturedInfo.DeclInfoMap) {
+    const auto &DeclInfo = KeyVal.second;
+    const ValueDecl *VD = dyn_cast_or_null<ValueDecl>(DeclInfo.TheDecl);
+    bool WillBeParameter = (DeclInfo.DeclaredIn == ZoneRelative::Before &&
+                            DeclInfo.IsReferencedInSource) ||
+                           (DeclInfo.DeclaredIn == ZoneRelative::Inside &&
+                            DeclInfo.IsReferencedInPostSource);
+    // Check if the Decl will become a parameter.
+    if (!WillBeParameter)
+      continue;
+    // Parameter specific checks.
+    // Can't parameterise if the Decl isn't a ValueDecl or is a FunctionDecl
+    // (this includes the case of recursive call to EnclosingFunc in Source).
+    if (!VD || dyn_cast_or_null<FunctionDecl>(DeclInfo.TheDecl))
+      return false;
+    // FIXME: Need better qualifier checks: check mutated status for
+    // DeclInformation
+    // FIXME: check if parameter will be a non l-value reference.
+    // FIXME: We don't want to always pass variables of types like int,
+    // pointers, etc by reference.
+    bool IsConstDecl = VD->getType().isConstQualified();
+    // We use the index of declaration as the ordering priority for parameters.
+    ExtractedFunc.addParam(VD->getName(), GetDeclType(VD), IsConstDecl,
+                           DeclInfo.DeclarationIndex);
+    // If a Decl was Declared in source and referenced in post source, it needs
+    // to be hoisted (we bail out in that case).
+    // FIXME: Support Decl Hoisting.
+    if (DeclInfo.DeclaredIn == ZoneRelative::Inside &&
+        DeclInfo.IsReferencedInPostSource)
+      return false;
+  }
+  llvm::sort(ExtractedFunc.Parameters);
+  return true;
+}
+
+// Clangd uses open ranges while ExtractionSemicolonPolicy (in Clang Tooling)
+// uses closed ranges. Generates the semicolon policy for the extraction and
+// extends the ZoneRange if necessary.
+tooling::ExtractionSemicolonPolicy
+getSemicolonPolicy(ExtractionZone &ExtZone, const SourceManager &SM,
+                   const LangOptions &LangOpts) {
+  // Get closed ZoneRange.
+  SourceRange FuncBodyRange = {ExtZone.ZoneRange.getBegin(),
+                               ExtZone.ZoneRange.getEnd().getLocWithOffset(-1)};
+  auto SemicolonPolicy = tooling::ExtractionSemicolonPolicy::compute(
+      ExtZone.getLastRootStmt()->ASTNode.get<Stmt>(), FuncBodyRange, SM,
+      LangOpts);
+  // Update ZoneRange.
+  ExtZone.ZoneRange.setEnd(FuncBodyRange.getEnd().getLocWithOffset(1));
+  return SemicolonPolicy;
+}
+
+// Generate return type for ExtractedFunc. Return false if unable to do so.
+bool generateReturnProperties(NewFunction &ExtractedFunc,
+                              const CapturedSourceInfo &CapturedInfo) {
+
+  // FIXME: Use Existing Return statements (if present)
+  // FIXME: Generate new return statement if needed.
+  if (CapturedInfo.HasReturnStmt)
+    return false;
+  ExtractedFunc.ReturnType = "void";
+  return true;
+}
+
+// FIXME: add support for adding other function return types besides void.
+// FIXME: assign the value returned by non void extracted function.
+llvm::Optional<NewFunction> getExtractedFunction(ExtractionZone &ExtZone,
+                                                 const SourceManager &SM,
+                                                 const LangOptions &LangOpts) {
+  CapturedSourceInfo CapturedInfo = CapturedSourceInfo::captureInfo(ExtZone);
+  // If there is any reference or source has a recursive call, we don't extract
+  // for now.
+  if (CapturedInfo.HasBreakOrContinue)
+    return llvm::None;
+  auto SemicolonPolicy = getSemicolonPolicy(ExtZone, SM, LangOpts);
+  NewFunction ExtractedFunc(ExtZone.ZoneRange, ExtZone.getInsertionPoint(),
+                            std::move(SemicolonPolicy), SM);
+  if (!createParameters(ExtractedFunc, CapturedInfo))
+    return llvm::None;
+  if (!generateReturnProperties(ExtractedFunc, CapturedInfo))
+    return llvm::None;
+  return ExtractedFunc;
+}
+
+/// Extracts statements to a new function and replaces the statements with a
+/// call to the new function.
+class ExtractFunction : public Tweak {
+public:
+  const char *id() const override final;
+
+  bool prepare(const Selection &Inputs) override;
+  Expected<Effect> apply(const Selection &Inputs) override;
+  std::string title() const override { return "Extract to function"; }
+  Intent intent() const override { return Refactor; }
+
+private:
+  std::shared_ptr<ExtractionZone> ExtZone;
+};
+
+REGISTER_TWEAK(ExtractFunction)
+tooling::Replacement replaceWithFuncCall(const NewFunction &ExtractedFunc,
+                                         const SourceManager &SM,
+                                         const LangOptions &LangOpts) {
+  std::string FuncCall = ExtractedFunc.renderCall();
+  return tooling::Replacement(
+      SM, CharSourceRange(ExtractedFunc.BodyRange, false), FuncCall, LangOpts);
+}
+
+tooling::Replacement createFunctionDefinition(const NewFunction &ExtractedFunc,
+                                              const SourceManager &SM) {
+  std::string FunctionDef = ExtractedFunc.renderDefinition();
+  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.getASTContext().getLangOpts();
+  ExtZone = getExtractionZone(CommonAnc, SM, LangOpts);
+  return (bool)ExtZone;
+}
+
+Expected<Tweak::Effect> ExtractFunction::apply(const Selection &Inputs) {
+  const SourceManager &SM = Inputs.AST.getSourceManager();
+  const LangOptions &LangOpts = Inputs.AST.getASTContext().getLangOpts();
+  auto ExtractedFunc = getExtractedFunction(*ExtZone, SM, LangOpts);
+  // FIXME: Add more types of errors.
+  if (!ExtractedFunc)
+    return llvm::createStringError(llvm::inconvertibleErrorCode(),
+                                   +"Too complex to extract.");
+  tooling::Replacements Result;
+  if (auto Err = Result.add(createFunctionDefinition(*ExtractedFunc, SM)))
+    return std::move(Err);
+  if (auto Err = Result.add(replaceWithFuncCall(*ExtractedFunc, SM, LangOpts)))
+    return std::move(Err);
+  return Effect::applyEdit(Result);
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

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

TEST_F(ExpandAutoTypeTest, Test) {
   // local class
   EXPECT_EQ(apply("namespace x { void y() { struct S{}; ^auto z = S(); } }"),
             "namespace x { void y() { struct S{}; S z = S(); } }");
   // replace array types
   EXPECT_EQ(apply(R"cpp(au^to x = "test")cpp"),
             R"cpp(const char * x = "test")cpp");
 }
 
+TWEAK_TEST(ExtractFunction);
+TEST_F(ExtractFunctionTest, FunctionTest) {
+  Header = R"cpp(
+    #define F(BODY) void FFF() { BODY }
+  )cpp";
+  Context = Function;
+
+  // 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");
+  // FIXME: Add tests for macros after selectionTree works properly for macros.
+  // FIXME: This should be extractable
+  EXPECT_EQ(apply("F ([[int x = 0;]])"), "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(;;) { [[{}]]break; }"), HasSubstr("extracted"));
+  // FIXME: This should be unavailable since partially selected but
+  // selectionTree doesn't always work correctly for VarDecls.
+  EXPECT_THAT(apply("int [[x = 0]];"), HasSubstr("extracted"));
+  // FIXME: ExtractFunction should be unavailable inside loop construct
+  // initalizer/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"));
+  // Don't extract return
+  EXPECT_THAT(apply(" if(true) [[return;]] "), StartsWith("fail"));
+  // Don't extract break and continue.
+  // FIXME: We should be able to extract this since it's non broken.
+  EXPECT_THAT(apply(" [[for(;;) break;]] "), StartsWith("fail"));
+  EXPECT_THAT(apply(" for(;;) [[continue;]] "), StartsWith("fail"));
+}
+
+TEST_F(ExtractFunctionTest, FileTest) {
+  // Check all parameters are in order
+  std::string ParameterCheckInput = R"cpp(
+struct FOO {
+  int x;
+};
+void f(int a) {
+  int b; int *ptr = &a; FOO foo;
+  [[a += foo.x + b;
+  *ptr++;]]
+})cpp";
+  std::string ParameterCheckOutput = R"cpp(
+struct FOO {
+  int x;
+};
+void extracted(int &a, int &b, int * &ptr, struct FOO &foo) {
+a += foo.x + b;
+  *ptr++;
+}
+void f(int a) {
+  int b; int *ptr = &a; FOO foo;
+  extracted(a, b, ptr, foo);
+})cpp";
+  EXPECT_EQ(apply(ParameterCheckInput), ParameterCheckOutput);
+
+  // Check const qualifier
+  std::string ConstCheckInput = R"cpp(
+void f(const int c) {
+  [[while(c) {}]]
+})cpp";
+  std::string ConstCheckOutput = R"cpp(
+void extracted(const int &c) {
+while(c) {}
+}
+void f(const int c) {
+  extracted(c);
+})cpp";
+  EXPECT_EQ(apply(ConstCheckInput), ConstCheckOutput);
+
+  // Don't extract when we need to make a function as a parameter.
+  EXPECT_THAT(apply("void f() { [[int a; f();]] }"), StartsWith("fail"));
+
+  // We don't extract from methods for now since they may involve multi-file
+  // edits
+  std::string MethodFailInput = R"cpp(
+    class T {
+      void f() {
+        [[int x;]]
+      }
+    };
+  )cpp";
+  EXPECT_EQ(apply(MethodFailInput), "unavailable");
+
+  // We don't extract from templated functions for now as templates are hard
+  // to deal with.
+  std::string TemplateFailInput = R"cpp(
+    template<typename T>
+    void f() {
+      [[int x;]]
+    }
+  )cpp";
+  EXPECT_EQ(apply(TemplateFailInput), "unavailable");
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang