[clangd] Fall back to selecting token-before-cursor if token-after-cursor fails.

[sammccall]

Summary

The problem:

LSP specifies that Positions are between characters. Therefore when a position
(or an empty range) is used to target elements of the source code, there is an
ambiguity - should we look left or right of the cursor?

Until now, SelectionTree resolved this to the right except in trivial cases
(where there's whitespace, semicolon, or eof on the right).
This meant that it's unable to e.g. out-line int foo^() today.

Complicating this, LSP notwithstanding the cursor is *on* a character in many
editors (mostly terminal-based). In these cases there's no ambiguity - we must
"look right" - but there's also no way to tell in LSP.

(Several features currently resolve this by using getBeginningOfIdentifier,
which tries to rewind and supports end-of-identifier. But this relies on
raw lexing and is limited and buggy).

Precedent: well - most other languages aren't so full of densely packed symbols
that we might want to target. Bias-towards-identifier works well enough.
MS C++ for vscode seems to mostly use bias-toward-identifier too.
The problem with this solution is it doesn't provide any way to target some
things such as the constructor call in Foo^(bar());

Presented solution:

When an ambiguous selection is found, we generate *both* possible selection
trees. We try to run the feature on the rightward tree first, and then on the
leftward tree if it fails.

This is basically do-what-I-mean, the main downside is the need to do this on
a feature-by-feature basis (because each feature knows what "fail" means).
The most complicated instance of this is Tweaks, where the preferred selection
may vary tweak-by-tweak.

[sammccall]

This needs tests, but wanted to share the ideas.

[sammccall]

Make tweaktests do the fallback dance so that they test how the feature actually works.

[merge_guards_bot]

clang-format: pass.

Build artifacts: console-log.txt, CMakeCache.txt, diff.json

[sammccall]

Use callbacks to avoid creating too many trees eagerly. Add tests.

[sammccall]

So a reasonable outcome here is we conclude this does more harm than good.
If that happens, I'd like to be clear on whether we have a better way of doing this in general or just don't think it's worth the cost, and should hack around it where possible as in D71284

[merge_guards_bot]

Unit tests: pass. 60717 tests passed, 0 failed and 726 were skipped.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or apply this patch.

Build artifacts: console-log.txt, CMakeCache.txt, clang-format.patch, test-results.xml, diff.json

[nridge]

I tried to do a less general version of this (for go-to-definition only) in D70727 :)

[sammccall]

In D71345#1780632, @nridge wrote:

I tried to do a less general version of this (for go-to-definition only) in D70727 :)

Ah, I hadn't seen that. After thinking about this a bit, I think the behavior in that patch is OK, and it's complexity that will do us in. More cases keep coming up - internally people complained about this in code actions which is the hardest case to fix and needs most of this complexity.

How do you feel about the approach here? I like having the description of the problem centralized and directing callsites toward a solution.
At the same time, it does make me sad that a fairly nice abstraction becomes so much harder to pick up and use, the API is pretty horrendous.

[nridge]

In D71345#1781141, @sammccall wrote:

How do you feel about the approach here?

I agree that having more of the logic centralized (in SelectionTree) is preferable to having it directly in a call site like getDeclAtPosition.

I also agree that this makes the SelectionTree API a bit clunky.

I tested the behaviour in Eclipse CDT, on the following testcase:

struct Material {
    friend Material operator+(Material, Material);
};

void foo() {
    Material hydrogen, oxygen;
    hydrogen^+^oxygen;
}

Here, both navigations target the overloaded operator, but if you comment out the overloaded operator, they target the respective local variable declarations. I think this is pretty good do-what-I-mean behaviour, arguably better than a categorical preference for the right side over the left side.

I can describe how CDT achieves this:

• There is an API that takes a textual selection, and an AST node type, and finds the innermost node of that type that encloses the selection.
• The AST nodes built for the statement are as follows:

hydrogen+oxygen;
AAAAAAAABCCCCCC;   // A and C have type Name, B has type ImplicitName

• (If the overloaded operator is commented out, there is no node B.)
• For the purpose of determining "encloses", the cursor being at either boundary of a node counts as a match (so A and B are both considered to enclose the first cursor, and B and C are both considered to enclose the second cursor).
• The algorithm for go-to-definition is: first look for an enclosing ImplicitName node; if one is found, go to its target. Otherwise, look for an enclosing Name node and go to its target.

Other features use the same API, but perhaps with a different node type; for example, the "define out of line" refactoring looks for an enclosing FunctionDeclarator node.

Perhaps we could have a simpler SelectionTree API along these lines, where the type of desired node informs the selection at each call site?

[sammccall]

In D71345#1782647, @nridge wrote:

Here, both navigations target the overloaded operator, but if you comment out the overloaded operator, they target the respective local variable declarations. I think this is pretty good do-what-I-mean behaviour, arguably better than a categorical preference for the right side over the left side.

That's reasonable in eclipse (though personally I'd find it frustrating to have no way to target b in a+b+c).
It seems broken for editors where the cursor is on a character rather than between characters, though.

• For the purpose of determining "encloses", the cursor being at either boundary of a node counts as a match (so A and B are both considered to enclose the first cursor, and B and C are both considered to enclose the second cursor).
• The algorithm for go-to-definition is: first look for an enclosing ImplicitName node; if one is found, go to its target. Otherwise, look for an enclosing Name node and go to its target.

Other features use the same API, but perhaps with a different node type; for example, the "define out of line" refactoring looks for an enclosing FunctionDeclarator node.

Perhaps we could have a simpler SelectionTree API along these lines, where the type of desired node informs the selection at each call site?

Thanks for the details on CDT. This diverges quite a lot from what we currently have:

• we have abstractions at the preprocessor level (tokens) and at the semantic level (clang AST), but nothing modeling the concept of e.g. "name" that we would need here.
• our refactorings (tweak) relies on computing the selection by traversing the AST first and then querying it for each operation, which doesn't work if the query affects the traversal and the traversal is expensive

Syntax trees would address this by providing a tree with the relevant syntactic constructs that's cheap to traverse, and would certainly end up replacing SelectionTree altogether.

[kadircet]

tl;dr; LGTM, from my side as long as you are also happy with the extra complexity introduced by this to all call sites.

As told in the offline discussions, only problem I have with this approach is its intrusiveness. But arguably all of the call sites that cares about what to do in such situations already has some sort of handling themselves. So I am OK with landing this generic situation and adding some more mental overhead to all of the callers, hopefully we could come up with some helpers that would enable callers to choose one behavior or the other all the time and get rid of extra complexity(not sure if they are likely to stick though).

[nridge]

In D71345#1783092, @sammccall wrote:

(though personally I'd find it frustrating to have no way to target b in a+b+c).

(For completeness, there is a way to target b in a+b+c: by selecting b (such that your selection range has length 1 rather than 0). Then, neither + node will enclose the selection range, but the b node will.)

[sammccall]

In D71345#1783579, @nridge wrote:

In D71345#1783092, @sammccall wrote:

(though personally I'd find it frustrating to have no way to target b in a+b+c).

(For completeness, there is a way to target b in a+b+c: by selecting b (such that your selection range has length 1 rather than 0). Then, neither + node will enclose the selection range, but the b node will.)

Indeed, sorry - I meant that if we incorporated it into an LSP server, there'd be no way to target it in methods that take a position rather than a selection (go to defn, hover etc).

[kadircet]

In D71345#1783579, @nridge wrote:

(For completeness, there is a way to target b in a+b+c: by selecting b (such that your selection range has length 1 rather than 0). Then, neither + node will enclose the selection range, but the b node will.)

yes but this doesn't work with most of the LSP features, e.g. go-to-def, hover, etc.

clang-tools-extra/clangd/ClangdServer.cpp

443

nit: no need for else

[sammccall]

OK, I'm going to land this with some reservations. It's a mess, but the number of callsites isn't overwhelming.
I'd been hoping to get away with bias-right, but we keep getting complaints about this.
It's hard to find an approach that solves this, doesn't obviously break other things, and is close enough to what we do now.
Happy to revisit in future, would be nice to get rid of this wart.

[sammccall]

Bias selection-tree right for Hover.
In VSCode (and presumably other GUI-based editors) the location sent is always
the one on the left of the character under the cursor.

Clang-format.

[nridge]

In D71345#1783587, @sammccall wrote:

Indeed, sorry - I meant that if we incorporated it into an LSP server, there'd be no way to target it in methods that take a position rather than a selection (go to defn, hover etc).

Ah, right, I forgot that LSP tends to send positions rather than ranges as inputs. (I hope that changes in the future, e.g. an issue is on file for hover.)

[merge_guards_bot]

Unit tests: pass. 60850 tests passed, 0 failed and 726 were skipped.

clang-format: pass.

Build artifacts: console-log.txt, CMakeCache.txt, test-results.xml, diff.json

[thakis]

This breaks compile on most bots in the "clang" section on http://lab.llvm.org:8011/console , probably the ones that use gcc as host compiler.

Here's an example:
http://lab.llvm.org:8011/builders/clang-cmake-armv7-selfhost-neon/builds/2714/steps/build%20stage%201/logs/stdio

[thakis]

Reverted in f0604e73a4daa35a10eb17a998657d6c4bd0e971

clang-tools-extra/clangd/ClangdServer.cpp

if (WantFormat) {
       if (Err)
         return CB(std::move(Err));
     }
     return CB(std::move(*Edits));
   };
   WorkScheduler.runWithAST("Rename", File, std::move(Action));
 }
 
-static llvm::Expected<Tweak::Selection>
+// May generate several candidate selections, due to SelectionTree ambiguity.
+static llvm::Expected<std::vector<Tweak::Selection>>
 tweakSelection(const Range &Sel, const InputsAndAST &AST) {
   auto Begin = positionToOffset(AST.Inputs.Contents, Sel.start);
   if (!Begin)
     return Begin.takeError();
   auto End = positionToOffset(AST.Inputs.Contents, Sel.end);
   if (!End)
     return End.takeError();
-  return Tweak::Selection(AST.Inputs.Index, AST.AST, *Begin, *End);
+  std::vector<Tweak::Selection> Result;
+  SelectionTree::createEach(AST.AST.getASTContext(), AST.AST.getTokens(),
+                            *Begin, *End, [&](SelectionTree T) {
+                              Result.emplace_back(AST.Inputs.Index, AST.AST,
+                                                  *Begin, *End, std::move(T));
+                              return false;
+                            });
+  assert(!Result.empty() && "Expected at least one SelectionTree");
+  return Result;
 }
 
 void ClangdServer::enumerateTweaks(PathRef File, Range Sel,
                                    Callback<std::vector<TweakRef>> CB) {
   auto Action = [File = File.str(), Sel, CB = std::move(CB),
                  this](Expected<InputsAndAST> InpAST) mutable {
     if (!InpAST)
       return CB(InpAST.takeError());
-    auto Selection = tweakSelection(Sel, *InpAST);
-    if (!Selection)
-      return CB(Selection.takeError());
+    auto Selections = tweakSelection(Sel, *InpAST);
+    if (!Selections)
+      return CB(Selections.takeError());
     std::vector<TweakRef> Res;
-    for (auto &T : prepareTweaks(*Selection, TweakFilter))
+    // Don't allow a tweak to fire more than once across ambiguous selections.
+    llvm::DenseSet<llvm::StringRef> PreparedTweaks;
+    auto Filter = [&](const Tweak &T) {
+      return TweakFilter(T) && !PreparedTweaks.count(T.id());
+    };
+    for (const auto &Sel : *Selections) {
+      for (auto &T : prepareTweaks(Sel, Filter)) {
         Res.push_back({T->id(), T->title(), T->intent()});
+        PreparedTweaks.insert(T->id());
+      }
+    }
 
     CB(std::move(Res));
   };
 
   WorkScheduler.runWithAST("EnumerateTweaks", File, std::move(Action));
 }
 
 void ClangdServer::applyTweak(PathRef File, Range Sel, StringRef TweakID,
                               Callback<Tweak::Effect> CB) {
   auto Action =
       [File = File.str(), Sel, TweakID = TweakID.str(), CB = std::move(CB),
        FS = FSProvider.getFileSystem()](Expected<InputsAndAST> InpAST) mutable {
         if (!InpAST)
           return CB(InpAST.takeError());
-        auto Selection = tweakSelection(Sel, *InpAST);
-        if (!Selection)
-          return CB(Selection.takeError());
-        auto A = prepareTweak(TweakID, *Selection);
-        if (!A)
-          return CB(A.takeError());
-        auto Effect = (*A)->apply(*Selection);
-        if (!Effect)
-          return CB(Effect.takeError());
-        for (auto &It : Effect->ApplyEdits) {
+        auto Selections = tweakSelection(Sel, *InpAST);
+        if (!Selections)
+          return CB(Selections.takeError());
+        llvm::Optional<llvm::Expected<Tweak::Effect>> Effect;
+        // Try each selection, take the first one that prepare()s.
+        // If they all fail, Effect will hold get the last error.
+        for (const auto &Selection : *Selections) {
+          auto T = prepareTweak(TweakID, Selection);
+          if (T) {
+            Effect = (*T)->apply(Selection);
+            break;
+          }
+          Effect = T.takeError();
+        }
+        assert(Effect.hasValue() && "Expected at least one selection");
+        if (*Effect) {
+          // Tweaks don't apply clang-format, do that centrally here.
+          for (auto &It : (*Effect)->ApplyEdits) {
             Edit &E = It.second;
             format::FormatStyle Style =
                 getFormatStyleForFile(File, E.InitialCode, FS.get());
             if (llvm::Error Err = reformatEdit(E, Style))
               elog("Failed to format {0}: {1}", It.first(), std::move(Err));
           }
+        }
         return CB(std::move(*Effect));
       };
   WorkScheduler.runWithAST("ApplyTweak", File, std::move(Action));
 }
 
 void ClangdServer::dumpAST(PathRef File,
                            llvm::unique_function<void(std::string)> Callback) {
   auto Action = [Callback = std::move(Callback)](

clang-tools-extra/clangd/Hover.cpp

llvm::Optional<HoverInfo> getHover(ParsedAST &AST, Position Pos,
   } else if (auto M = locateMacroAt(SourceLocationBeg, AST.getPreprocessor())) {
     HI = getHoverContents(*M, AST);
   } else {
     auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
     if (!Offset) {
       llvm::consumeError(Offset.takeError());
       return llvm::None;
     }
-    SelectionTree Selection(AST.getASTContext(), AST.getTokens(), *Offset);
+    // Editors send the position on the left of the hovered character.
+    // So our selection tree should be biased right. (Tested with VSCode).
+    SelectionTree ST = SelectionTree::createRight(
+        AST.getASTContext(), AST.getTokens(), *Offset, *Offset);
     std::vector<const Decl *> Result;
-    if (const SelectionTree::Node *N = Selection.commonAncestor()) {
+    if (const SelectionTree::Node *N = ST.commonAncestor()) {
       DeclRelationSet Rel = DeclRelation::TemplatePattern | DeclRelation::Alias;
       auto Decls = targetDecl(N->ASTNode, Rel);
       if (!Decls.empty()) {
         HI = getHoverContents(Decls.front(), Index);
         // Look for a close enclosing expression to show the value of.
         if (!HI->Value)
           HI->Value = printExprValue(N, AST.getASTContext());
       }

clang-tools-extra/clangd/Selection.h

 //   if (err) {          // reference to 'err', or operator bool(),
 //       ^               // or the if statement itself?
 //
 // Here we build and expose a data structure that allows features to resolve
 // these ambiguities in an appropriate way:
 //   - we determine which low-level nodes are partly or completely covered
 //     by the selection.
 //   - we expose a tree of the selected nodes and their lexical parents.
+//
+// Sadly LSP specifies locations as being between characters, and this causes
+// some ambiguities we cannot cleanly resolve:
+//   lhs+rhs  // targeting '+' or 'lhs'?
+//      ^     // in GUI editors, double-clicking 'lhs' yields this position!
+//
+// The best we can do in these cases is try both, which leads to the awkward
+// SelectionTree::createEach() API.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SELECTION_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SELECTION_H
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/SmallVector.h"

 //
 // Comments, directives and whitespace are completely ignored.
 // Semicolons are also ignored, as the AST generally does not model them well.
 //
 // The SelectionTree owns the Node structures, but the ASTNode attributes
 // point back into the AST it was constructed with.
 class SelectionTree {
 public:
-  // Creates a selection tree at the given byte offset in the main file.
-  // This is approximately equivalent to a range of one character.
-  // (Usually, the character to the right of Offset, sometimes to the left).
-  SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
-                unsigned Offset);
-  // Creates a selection tree for the given range in the main file.
-  // The range includes bytes [Start, End).
-  // If Start == End, uses the same heuristics as SelectionTree(AST, Start).
-  SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
-                unsigned Start, unsigned End);
+  // Create selection trees for the given range, and pass them to Func.
+  //
+  // There may be multiple possible selection trees:
+  // - if the range is empty and borders two tokens, a tree for the right token
+  //   and a tree for the left token will be yielded.
+  // - Func should return true on success (stop) and false on failure (continue)
+  //
+  // Always yields at least one tree. If no tokens are touched, it is empty.
+  static bool createEach(ASTContext &AST, const syntax::TokenBuffer &Tokens,
+                         unsigned Begin, unsigned End,
+                         llvm::function_ref<bool(SelectionTree)> Func);
+
+  // Create a selection tree for the given range.
+  //
+  // Where ambiguous (range is empty and borders two tokens), prefer the token
+  // on the right.
+  static SelectionTree createRight(ASTContext &AST,
+                                   const syntax::TokenBuffer &Tokens,
+                                   unsigned Begin, unsigned End);
+
+  // Copies are no good - contain pointers to other nodes.
+  SelectionTree(const SelectionTree &) = delete;
+  SelectionTree &operator=(const SelectionTree &) = delete;
+  // Moves are OK though - internal storage is pointer-stable when moved.
+  SelectionTree(SelectionTree &&) = default;
+  SelectionTree &operator=(SelectionTree &&) = default;
 
   // Describes to what extent an AST node is covered by the selection.
   enum Selection : unsigned char {
     // The AST node owns no characters covered by the selection.
     // Note that characters owned by children don't count:
     //   if (x == 0) scream();
     //       ^^^^^^
     // The IfStmt would be Unselected because all the selected characters are
public:
   // The most specific common ancestor of all the selected nodes.
   // Returns nullptr if the common ancestor is the root.
   // (This is to avoid accidentally traversing the TUDecl and thus preamble).
   const Node *commonAncestor() const;
   // The selection node corresponding to TranslationUnitDecl.
   const Node &root() const { return *Root; }
 
 private:
+  // Creates a selection tree for the given range in the main file.
+  // The range includes bytes [Start, End).
+  SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
+                unsigned Start, unsigned End);
+
   std::deque<Node> Nodes; // Stable-pointer storage.
   const Node *Root;
   clang::PrintingPolicy PrintPolicy;
 
   void print(llvm::raw_ostream &OS, const Node &N, int Indent) const;
   friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                        const SelectionTree &T) {
     T.print(OS, T.root(), 1);
     return OS;
   }
 };
 
 } // namespace clangd
 } // namespace clang
 #endif

clang-tools-extra/clangd/Selection.cpp

if (New == NoTokens)
     return;
   if (Result == NoTokens)
     Result = New;
   else if (Result != New)
     // Can only be completely selected (or unselected) if all tokens are.
     Result = SelectionTree::Partial;
 }
 
+// As well as comments, don't count semicolons as real tokens.
+// They're not properly claimed as expr-statement is missing from the AST.
+bool shouldIgnore(const syntax::Token &Tok) {
+  return Tok.kind() == tok::comment || Tok.kind() == tok::semi;
+}
 
 // SelectionTester can determine whether a range of tokens from the PP-expanded
 // stream (corresponding to an AST node) is considered selected.
 //
 // When the tokens result from macro expansions, the appropriate tokens in the
 // main file are examined (macro invocation or args). Similarly for #includes.
 //
 // It tests each token in the range (not just the endpoints) as contiguous
const syntax::Token *SelFirst =
           return SM.getFileOffset(Tok.endLocation()) <= SelBegin;
         });
     const syntax::Token *SelLimit = std::partition_point(
         SelFirst, AllSpelledTokens.end(), [&](const syntax::Token &Tok) {
           return SM.getFileOffset(Tok.location()) < SelEnd;
         });
     // Precompute selectedness and offset for selected spelled tokens.
     for (const syntax::Token *T = SelFirst; T < SelLimit; ++T) {
-      // As well as comments, don't count semicolons as real tokens.
-      // They're not properly claimed as expr-statement is missing from the AST.
-      if (T->kind() == tok::comment || T->kind() == tok::semi)
+      if (shouldIgnore(*T))
         continue;
       SpelledTokens.emplace_back();
       Tok &S = SpelledTokens.back();
       S.Offset = SM.getFileOffset(T->location());
       if (S.Offset >= SelBegin && S.Offset + T->length() <= SelEnd)
         S.Selected = SelectionTree::Complete;
       else
         S.Selected = SelectionTree::Partial;

 
 std::string SelectionTree::Node::kind() const {
   std::string S;
   llvm::raw_string_ostream OS(S);
   printNodeKind(OS, ASTNode);
   return std::move(OS.str());
 }
 
-// Decide which selection emulates a "point" query in between characters.
-static std::pair<unsigned, unsigned> pointBounds(unsigned Offset, FileID FID,
-                                                 ASTContext &AST) {
-  StringRef Buf = AST.getSourceManager().getBufferData(FID);
-  // Edge-cases where the choice is forced.
-  if (Buf.size() == 0)
-    return {0, 0};
-  if (Offset == 0)
-    return {0, 1};
-  if (Offset == Buf.size())
-    return {Offset - 1, Offset};
-  // We could choose either this byte or the previous. Usually we prefer the
-  // character on the right of the cursor (or under a block cursor).
-  // But if that's whitespace/semicolon, we likely want the token on the left.
-  auto IsIgnoredChar = [](char C) { return isWhitespace(C) || C == ';'; };
-  if (IsIgnoredChar(Buf[Offset]) && !IsIgnoredChar(Buf[Offset - 1]))
-    return {Offset - 1, Offset};
-  return {Offset, Offset + 1};
+// Decide which selections emulate a "point" query in between characters.
+// If it's ambiguous (the neighboring characters are selectable tokens), returns
+// both possibilities in preference order.
+// Always returns at least one range - if no tokens touched, and empty range.
+static llvm::SmallVector<std::pair<unsigned, unsigned>, 2>
+pointBounds(unsigned Offset, const syntax::TokenBuffer &Tokens) {
+  const auto &SM = Tokens.sourceManager();
+  SourceLocation Loc = SM.getComposedLoc(SM.getMainFileID(), Offset);
+  llvm::SmallVector<std::pair<unsigned, unsigned>, 2> Result;
+  // Prefer right token over left.
+  for (const syntax::Token &Tok :
+       llvm::reverse(spelledTokensTouching(Loc, Tokens))) {
+    if (shouldIgnore(Tok))
+      continue;
+    unsigned Offset = Tokens.sourceManager().getFileOffset(Tok.location());
+    Result.emplace_back(Offset, Offset + Tok.length());
+  }
+  if (Result.empty())
+    Result.emplace_back(Offset, Offset);
+  return Result;
+}
+
+bool SelectionTree::createEach(ASTContext &AST,
+                               const syntax::TokenBuffer &Tokens,
+                               unsigned Begin, unsigned End,
+                               llvm::function_ref<bool(SelectionTree)> Func) {
+  if (Begin != End)
+    return Func(SelectionTree(AST, Tokens, Begin, End));
+  for (std::pair<unsigned, unsigned> Bounds : pointBounds(Begin, Tokens))
+    if (Func(SelectionTree(AST, Tokens, Bounds.first, Bounds.second)))
+      return true;
+  return false;
+}
+
+SelectionTree SelectionTree::createRight(ASTContext &AST,
+                                         const syntax::TokenBuffer &Tokens,
+                                         unsigned int Begin, unsigned int End) {
+  llvm::Optional<SelectionTree> Result;
+  createEach(AST, Tokens, Begin, End, [&](SelectionTree T) {
+    Result = std::move(T);
+    return true;
+  });
+  return std::move(*Result);
 }
 
 SelectionTree::SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
                              unsigned Begin, unsigned End)
     : PrintPolicy(AST.getLangOpts()) {
   // No fundamental reason the selection needs to be in the main file,
   // but that's all clangd has needed so far.
   const SourceManager &SM = AST.getSourceManager();
   FileID FID = SM.getMainFileID();
-  if (Begin == End)
-    std::tie(Begin, End) = pointBounds(Begin, FID, AST);
   PrintPolicy.TerseOutput = true;
   PrintPolicy.IncludeNewlines = false;
 
   dlog("Computing selection for {0}",
        SourceRange(SM.getComposedLoc(FID, Begin), SM.getComposedLoc(FID, End))
            .printToString(SM));
   Nodes = SelectionVisitor::collect(AST, Tokens, PrintPolicy, Begin, End, FID);
   Root = Nodes.empty() ? nullptr : &Nodes.front();
   dlog("Built selection tree\n{0}", *this);
 }
 
-SelectionTree::SelectionTree(ASTContext &AST, const syntax::TokenBuffer &Tokens,
-                             unsigned Offset)
-    : SelectionTree(AST, Tokens, Offset, Offset) {}
-
 const Node *SelectionTree::commonAncestor() const {
   const Node *Ancestor = Root;
   while (Ancestor->Children.size() == 1 && !Ancestor->Selected)
     Ancestor = Ancestor->Children.front();
   // Returning nullptr here is a bit unprincipled, but it makes the API safer:
   // the TranslationUnitDecl contains all of the preamble, so traversing it is a
   // performance cliff. Callers can check for null and use root() if they want.
   return Ancestor != Root ? Ancestor : nullptr;

clang-tools-extra/clangd/SemanticSelection.cpp

llvm::Expected<std::vector<Range>> getSemanticRanges(ParsedAST &AST,
 
   auto FID = SM.getMainFileID();
   auto Offset = positionToOffset(SM.getBufferData(FID), Pos);
   if (!Offset) {
     return Offset.takeError();
   }
 
   // Get node under the cursor.
-  SelectionTree ST(AST.getASTContext(), AST.getTokens(), *Offset);
+  SelectionTree ST = SelectionTree::createRight(
+      AST.getASTContext(), AST.getTokens(), *Offset, *Offset);
   for (const auto *Node = ST.commonAncestor(); Node != nullptr;
        Node = Node->Parent) {
     if (const Decl *D = Node->ASTNode.get<Decl>()) {
       if (llvm::isa<TranslationUnitDecl>(D)) {
         break;
       }
     }
 

clang-tools-extra/clangd/XRefs.cpp

SymbolLocation getPreferredLocation(const Location &ASTLoc,
   ASTSym.CanonicalDeclaration = toIndexLocation(ASTLoc, Scratch);
   IdxSym.CanonicalDeclaration = IdxLoc;
   auto Merged = mergeSymbol(ASTSym, IdxSym);
   return Merged.CanonicalDeclaration;
 }
 
 std::vector<const Decl *> getDeclAtPosition(ParsedAST &AST, SourceLocation Pos,
                                             DeclRelationSet Relations) {
-  FileID FID;
-  unsigned Offset;
-  std::tie(FID, Offset) = AST.getSourceManager().getDecomposedSpellingLoc(Pos);
-  SelectionTree Selection(AST.getASTContext(), AST.getTokens(), Offset);
+  unsigned Offset = AST.getSourceManager().getDecomposedSpellingLoc(Pos).second;
   std::vector<const Decl *> Result;
-  if (const SelectionTree::Node *N = Selection.commonAncestor()) {
-    auto Decls = targetDecl(N->ASTNode, Relations);
-    Result.assign(Decls.begin(), Decls.end());
-  }
+  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
+                            Offset, [&](SelectionTree ST) {
+                              if (const SelectionTree::Node *N =
+                                      ST.commonAncestor())
+                                llvm::copy(targetDecl(N->ASTNode, Relations),
+                                           std::back_inserter(Result));
+                              return !Result.empty();
+                            });
   return Result;
 }
 
 llvm::Optional<Location> makeLocation(ASTContext &AST, SourceLocation TokLoc,
                                       llvm::StringRef TUPath) {
   const SourceManager &SourceMgr = AST.getSourceManager();
   const FileEntry *F = SourceMgr.getFileEntryForID(SourceMgr.getFileID(TokLoc));
   if (!F)

clang-tools-extra/clangd/refactor/Rename.cpp

llvm::Optional<std::string> getOtherRefFile(const Decl &D, StringRef MainFile,
   return OtherFile;
 }
 
 llvm::DenseSet<const Decl *> locateDeclAt(ParsedAST &AST,
                                           SourceLocation TokenStartLoc) {
   unsigned Offset =
       AST.getSourceManager().getDecomposedSpellingLoc(TokenStartLoc).second;
 
-  SelectionTree Selection(AST.getASTContext(), AST.getTokens(), Offset);
+  SelectionTree Selection = SelectionTree::createRight(
+      AST.getASTContext(), AST.getTokens(), Offset, Offset);
   const SelectionTree::Node *SelectedNode = Selection.commonAncestor();
   if (!SelectedNode)
     return {};
 
   llvm::DenseSet<const Decl *> Result;
   for (const auto *D :
        targetDecl(SelectedNode->ASTNode,
                   DeclRelation::Alias | DeclRelation::TemplatePattern)) {

clang-tools-extra/clangd/refactor/Tweak.h

 ///     // implement other methods here.
 ///   };
 ///   REGISTER_TWEAK(MyTweak);
 class Tweak {
 public:
   /// Input to prepare and apply tweaks.
   struct Selection {
     Selection(const SymbolIndex *Index, ParsedAST &AST, unsigned RangeBegin,
-              unsigned RangeEnd);
+              unsigned RangeEnd, SelectionTree ASTSelection);
     /// The text of the active document.
     llvm::StringRef Code;
     /// The Index for handling codebase related queries.
     const SymbolIndex *Index = nullptr;
     /// Parsed AST of the active file.
     ParsedAST *
     /// A location of the cursor in the editor.
     // FIXME: Cursor is redundant and should be removed

clang-tools-extra/clangd/refactor/Tweak.cpp

assert(E.instantiate()->id() == E.getName() &&
            "id should be equal to class name");
     assert(Seen.try_emplace(E.getName()).second && "duplicate check id");
   }
 #endif
 }
 } // namespace
 
 Tweak::Selection::Selection(const SymbolIndex *Index, ParsedAST &AST,
-                            unsigned RangeBegin, unsigned RangeEnd)
+                            unsigned RangeBegin, unsigned RangeEnd,
+                            SelectionTree ASTSelection)
     : Index(Index), AST(AST), SelectionBegin(RangeBegin),
-      SelectionEnd(RangeEnd),
-      ASTSelection(AST.getASTContext(), AST.getTokens(), RangeBegin, RangeEnd) {
+      SelectionEnd(RangeEnd), ASTSelection(std::move(ASTSelection)) {
   auto &SM = AST.getSourceManager();
   Code = SM.getBufferData(SM.getMainFileID());
   Cursor = SM.getComposedLoc(SM.getMainFileID(), RangeBegin);
 }
 
 std::vector<std::unique_ptr<Tweak>>
 prepareTweaks(const Tweak::Selection &S,
               llvm::function_ref<bool(const Tweak &)> Filter) {

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

protected:
   // Use via EXPECT_DECLS().
   std::vector<PrintedDecl> assertNodeAndPrintDecls(const char *NodeType) {
     llvm::Annotations A(Code);
     auto TU = TestTU::withCode(A.code());
     TU.ExtraArgs = Flags;
     auto AST = TU.build();
     EXPECT_THAT(AST.getDiagnostics(), ::testing::IsEmpty()) << Code;
     llvm::Annotations::Range R = A.range();
-    SelectionTree Selection(AST.getASTContext(), AST.getTokens(), R.Begin,
-                            R.End);
+    auto Selection = SelectionTree::createRight(
+        AST.getASTContext(), AST.getTokens(), R.Begin, R.End);
     const SelectionTree::Node *N = Selection.commonAncestor();
     if (!N) {
       ADD_FAILURE() << "No node selected!\n" << Code;
       return {};
     }
     EXPECT_EQ(N->kind(), NodeType) << Selection;
 
     std::vector<PrintedDecl> ActualDecls;

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

llvm::StringRef Tests[] = {
       R"cpp(// structured binding. Not supported yet
             struct Bar {};
             void foo() {
               Bar a[2];
               ^auto [x,y] = a;
             }
           )cpp",
       R"cpp(// Template auto parameter. Nothing (Not useful).
-            template<^auto T>
+            template<a^uto T>
             void func() {
             }
             void foo() {
                func<1>();
             }
           )cpp",
   };
 

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

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 using ::testing::UnorderedElementsAreArray;
 
+// Create a selection tree corresponding to a point or pair of points.
+// This uses the precisely-defined createRight semantics. The fuzzier
+// createEach is tested separately.
 SelectionTree makeSelectionTree(const StringRef MarkedCode, ParsedAST &AST) {
   Annotations Test(MarkedCode);
   switch (Test.points().size()) {
-  case 1: // Point selection.
-    return SelectionTree(AST.getASTContext(), AST.getTokens(),
-                         cantFail(positionToOffset(Test.code(), Test.point())));
+  case 1: { // Point selection.
+    unsigned Offset = cantFail(positionToOffset(Test.code(), Test.point()));
+    return SelectionTree::createRight(AST.getASTContext(), AST.getTokens(),
+                                      Offset, Offset);
+  }
   case 2: // Range selection.
-    return SelectionTree(
+    return SelectionTree::createRight(
         AST.getASTContext(), AST.getTokens(),
         cantFail(positionToOffset(Test.code(), Test.points()[0])),
         cantFail(positionToOffset(Test.code(), Test.points()[1])));
   default:
     ADD_FAILURE() << "Expected 1-2 points for selection.\n" << MarkedCode;
-    return SelectionTree(AST.getASTContext(), AST.getTokens(), 0u, 0u);
+    return SelectionTree::createRight(AST.getASTContext(), AST.getTokens(), 0u,
+                                      0u);
   }
 }
 
 Range nodeRange(const SelectionTree::Node *N, ParsedAST &AST) {
   if (!N)
     return Range{};
   const SourceManager &SM = AST.getSourceManager();
   const LangOptions &LangOpts = AST.getLangOpts();
TEST(SelectionTest, Implicit) {
   EXPECT_EQ("ImplicitCastExpr", nodeKind(Str->Parent));
   EXPECT_EQ("CXXConstructExpr", nodeKind(Str->Parent->Parent));
   EXPECT_EQ(Str, &Str->Parent->Parent->ignoreImplicit())
       << "Didn't unwrap " << nodeKind(&Str->Parent->Parent->ignoreImplicit());
 
   EXPECT_EQ("CXXConstructExpr", nodeKind(&Str->outerImplicit()));
 }
 
+TEST(SelectionTest, CreateAll) {
+  llvm::Annotations Test("int$unique^ a=1$ambiguous^+1; $empty^");
+  auto AST = TestTU::withCode(Test.code()).build();
+  unsigned Seen = 0;
+  SelectionTree::createEach(
+      AST.getASTContext(), AST.getTokens(), Test.point("ambiguous"),
+      Test.point("ambiguous"), [&](SelectionTree T) {
+        // Expect to see the right-biased tree first.
+        if (Seen == 0)
+          EXPECT_EQ("BinaryOperator", nodeKind(T.commonAncestor()));
+        else if (Seen == 1)
+          EXPECT_EQ("IntegerLiteral", nodeKind(T.commonAncestor()));
+        ++Seen;
+        return false;
+      });
+  EXPECT_EQ(2u, Seen);
+
+  Seen = 0;
+  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
+                            Test.point("ambiguous"), Test.point("ambiguous"),
+                            [&](SelectionTree T) {
+                              ++Seen;
+                              return true;
+                            });
+  EXPECT_EQ(1u, Seen) << "Return true --> stop iterating";
+
+  Seen = 0;
+  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
+                            Test.point("unique"), Test.point("unique"),
+                            [&](SelectionTree T) {
+                              ++Seen;
+                              return false;
+                            });
+  EXPECT_EQ(1u, Seen) << "no ambiguity --> only one tree";
+
+  Seen = 0;
+  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
+                            Test.point("empty"), Test.point("empty"),
+                            [&](SelectionTree T) {
+                              EXPECT_FALSE(T.commonAncestor());
+                              ++Seen;
+                              return false;
+                            });
+  EXPECT_EQ(1u, Seen) << "empty tree still created";
+
+  Seen = 0;
+  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
+                            Test.point("unique"), Test.point("ambiguous"),
+                            [&](SelectionTree T) {
+                              ++Seen;
+                              return false;
+                            });
+  EXPECT_EQ(1u, Seen) << "one tree for nontrivial selection";
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

if (A.points().size() != 0) {
     SelectionRng = Range{A.point(), A.point()};
   } else {
     SelectionRng = A.range();
   }
   return {cantFail(positionToOffset(A.code(), SelectionRng.start)),
           cantFail(positionToOffset(A.code(), SelectionRng.end))};
 }
 
+// Prepare and apply the specified tweak based on the selection in Input.
+// Returns None if and only if prepare() failed.
+llvm::Optional<llvm::Expected<Tweak::Effect>>
+applyTweak(ParsedAST &AST, const Annotations &Input, StringRef TweakID,
+           const SymbolIndex *Index) {
+  auto Range = rangeOrPoint(Input);
+  llvm::Optional<llvm::Expected<Tweak::Effect>> Result;
+  SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Range.first,
+                            Range.second, [&](SelectionTree ST) {
+                              Tweak::Selection S(Index, AST, Range.first,
+                                                 Range.second, std::move(ST));
+                              if (auto T = prepareTweak(TweakID, S)) {
+                                Result = (*T)->apply(S);
+                                return true;
+                              } else {
+                                llvm::consumeError(T.takeError());
+                                return false;
+                              }
+                            });
+  return Result;
+}
+
 MATCHER_P7(TweakIsAvailable, TweakID, Ctx, Header, ExtraArgs, ExtraFiles, Index,
            FileName,
            (TweakID + (negation ? " is unavailable" : " is available")).str()) {
   std::string WrappedCode = wrap(Ctx, arg);
   Annotations Input(WrappedCode);
-  auto Selection = rangeOrPoint(Input);
   TestTU TU;
   TU.Filename = FileName;
   TU.HeaderCode = Header;
   TU.Code = Input.code();
   TU.ExtraArgs = ExtraArgs;
   TU.AdditionalFiles = std::move(ExtraFiles);
   ParsedAST AST = TU.build();
-  Tweak::Selection S(Index, AST, Selection.first, Selection.second);
-  auto PrepareResult = prepareTweak(TweakID, S);
-  if (PrepareResult)
-    return true;
-  llvm::consumeError(PrepareResult.takeError());
-  return false;
+  auto Result = applyTweak(AST, Input, TweakID, Index);
+  // We only care if prepare() succeeded, but must handle Errors.
+  if (Result && !*Result)
+    consumeError(Result->takeError());
+  return Result.hasValue();
 }
 
 } // namespace
 
 std::string TweakTest::apply(llvm::StringRef MarkedCode,
                              llvm::StringMap<std::string> *EditedFiles) const {
   std::string WrappedCode = wrap(Context, MarkedCode);
   Annotations Input(WrappedCode);
-  auto Selection = rangeOrPoint(Input);
-
   TestTU TU;
   TU.Filename = FileName;
   TU.HeaderCode = Header;
   TU.AdditionalFiles = std::move(ExtraFiles);
   TU.Code = Input.code();
   TU.ExtraArgs = ExtraArgs;
   ParsedAST AST = TU.build();
-  Tweak::Selection S(Index.get(), AST, Selection.first, Selection.second);
 
-  auto T = prepareTweak(TweakID, S);
-  if (!T) {
-    llvm::consumeError(T.takeError());
-    return "unavailable";
-  }
-  llvm::Expected<Tweak::Effect> Result = (*T)->apply(S);
+  auto Result = applyTweak(AST, Input, TweakID, Index.get());
   if (!Result)
-    return "fail: " + llvm::toString(Result.takeError());
-  if (Result->ShowMessage)
-    return "message:\n" + *Result->ShowMessage;
-  if (Result->ApplyEdits.empty())
+    return "unavailable";
+  if (!*Result)
+    return "fail: " + llvm::toString(Result->takeError());
+  const auto &Effect = **Result;
+  if ((*Result)->ShowMessage)
+    return "message:\n" + *Effect.ShowMessage;
+  if (Effect.ApplyEdits.empty())
     return "no effect";
 
   std::string EditedMainFile;
-  for (auto &It : Result->ApplyEdits) {
+  for (auto &It : Effect.ApplyEdits) {
     auto NewText = It.second.apply();
     if (!NewText)
       return "bad edits: " + llvm::toString(NewText.takeError());
     llvm::StringRef Unwrapped = unwrap(Context, *NewText);
     if (It.first() == testPath(TU.Filename))
       EditedMainFile = Unwrapped;
     else {
       if (!EditedFiles)

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

EXPECT_UNAVAILABLE(R"cpp(
 
     [[void [[Bar::[[b^a^z]]]]() [[{
       return;
     }]]]])cpp");
 
   // Basic check for function body and signature.
   EXPECT_AVAILABLE(R"cpp(
     class Bar {
-      [[void [[f^o^o]]() [[{ return; }]]]]
+      [[void [[f^o^o^]]() [[{ return; }]]]]
     };
 
     void foo();
     [[void [[f^o^o]]() [[{
       return;
     }]]]])cpp");
 
   // Not available on defaulted/deleted members.