Use pseudo parser for folding ranges

[usaxena95]

Summary

This first version only uses bracket matching.
We plan to extend this to use DirectiveTree as well.

Also includes changes to Token to allow retrieving corresponding token
in token stream of original source file.

[usaxena95]

Addressed offline comments.

[usaxena95]

Removed changes from previous revision.

[hokein]

clang-tools-extra/clangd/SemanticSelection.cpp

183

nit: no need to use llvm::Optional.

186

Do we want to strip comments? I think we can keep the comments.

193

The if logic seems tricky, it is doing two different things:

1. avoid creating duplicate FoldingRange for a pair bracket
2. avoid creating a FoldingRange if the pair bracket is on the same line.

Are both intended?

195

the OrigStream.origToken syntax seems weird from the caller side (it is counter-intuitive).

I think OrigStream.tokens()[T.OrigTokIdx] is clearer.

clang-tools-extra/pseudo/include/clang-pseudo/Token.h

71

I'd suggest initializing it to Index::Invalid.

it'd be nice to add some tests in the pseudo/unittests/TokenTest.cpp.

181

I'm not sure we should have this API, it seems error-prone to use, and it only makes sense for the original token stream. (I'd just remove it, and use OrigStream.tokens()[T.OrigTokIdx] directly, see my other comment)

[sammccall]

clang-tools-extra/clangd/CMakeLists.txt

149

It should rather be up to the clangPseudo target to specify its include directories, if it doesn't already

I think interface_include_directories() is the right function (though knowing llvm maybe it's wrapped somehow)

https://cmake.org/cmake/help/latest/prop_tgt/INTERFACE_INCLUDE_DIRECTORIES.html

clang-tools-extra/clangd/SemanticSelection.cpp

164

we should transfer this fixme, either now or when we remove this code

184

This means we won't offer folding ranges in disabled-PP regions.
This is a significant regression of the client-side fallback!
It's not trivial to address though. Add a FIXME?

186

Stripping comments doesn't seem necessary to me, maybe I'm missing something.

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

263

You've removed the tests for the old implementation, but it's still used by ClangdServer.

Test both versions instead?

clang-tools-extra/pseudo/include/clang-pseudo/Token.h

70

nit: not clear what "original source file" is opposed to

maybe (as raw-lexed from the source code)

71

OriginalIndex (avoid cryptic abbreviations, "token" is implied)

175

I don't like the stream knowing about this attribute, there's no reasonable way to actually use it dynamically at runtime, we're complicating the API just so we can add some assertions.

What's wrong with OrigToken = OrigStream.tokens()[T.OrigIndex]?

(If we're going to teach the stream about the "derived stream" concept, it seems more natural to give it a pointer to its parent and allow mapping to any ancestor stream)

clang-tools-extra/pseudo/lib/Lex.cpp

30

nit: unsigned -> Token::Index
Idx -> Index? (it's not too cryptic here but also only saving 2 chars)

[usaxena95]

Addressed comments.

clang-tools-extra/clangd/SemanticSelection.cpp

193

Yes. Both of these are intentional. Added a comment.

[usaxena95]

Removed unused headers and fix spellings.

[hokein]

Thanks, this looks good.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   )
 
 # Include generated CompletionModel headers.
 target_include_directories(clangDaemon PUBLIC
   $<BUILD_INTERFACE:${CMAKE_CURRENT_BINARY_DIR}>
 )
 
 clang_target_link_libraries(clangDaemon
   PRIVATE
   clangAST
   clangASTMatchers
   clangBasic
   clangDriver
   clangFormat
   clangFrontend
   clangIndex
   clangLex
   clangSema
   clangSerialization
   clangTooling
   clangToolingCore
   clangToolingInclusions
   clangToolingSyntax
   )
 
 target_link_libraries(clangDaemon
   PRIVATE
   ${LLVM_PTHREAD_LIB}
 
   clangTidy
 
   clangdSupport
+
+  clangPseudo
   )
 if(CLANGD_TIDY_CHECKS)
   target_link_libraries(clangDaemon PRIVATE ${ALL_CLANG_TIDY_CHECKS})
 endif()
 
 add_subdirectory(refactor/tweaks)
 if (${CMAKE_SYSTEM_NAME} STREQUAL "Linux")
   # FIXME: Make fuzzer not use linux-specific APIs, build it everywhere.

clang-tools-extra/clangd/SemanticSelection.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SEMANTICSELECTION_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SEMANTICSELECTION_H
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "llvm/Support/Error.h"
+#include <string>
 #include <vector>
 namespace clang {
 namespace clangd {
 
 /// Returns the list of all interesting ranges around the Position \p Pos.
 /// The interesting ranges corresponds to the AST nodes in the SelectionTree
 /// containing \p Pos.
 /// If pos is not in any interesting range, return [Pos, Pos).
 llvm::Expected<SelectionRange> getSemanticRanges(ParsedAST &AST, Position Pos);
 
 /// Returns a list of ranges whose contents might be collapsible in an editor.
 /// This should include large scopes, preprocessor blocks etc.
 llvm::Expected<std::vector<FoldingRange>> getFoldingRanges(ParsedAST &AST);
 
+/// Returns a list of ranges whose contents might be collapsible in an editor.
+/// This version uses the pseudoparser which does not require the AST.
+llvm::Expected<std::vector<FoldingRange>>
+getFoldingRanges(const std::string &Code);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_SEMANTICSELECTION_H

clang-tools-extra/clangd/SemanticSelection.cpp

 //===--- SemanticSelection.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 "SemanticSelection.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "Selection.h"
 #include "SourceCode.h"
+#include "clang-pseudo/Bracket.h"
+#include "clang-pseudo/DirectiveTree.h"
+#include "clang-pseudo/Token.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Syntax/BuildTree.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "clang/Tooling/Syntax/TokenBufferTokenManager.h"
 #include "clang/Tooling/Syntax/Tree.h"
 #include "llvm/ADT/ArrayRef.h"
for (auto &Range :
     Tail->parent = std::make_unique<SelectionRange>();
     Tail = Tail->parent.get();
     Tail->range = std::move(Range);
   }
 
   return std::move(Head);
 }
 
 // FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and
 // other code regions (e.g. public/private/protected sections of classes,
 // control flow statement bodies).
 // Related issue: https://github.com/clangd/clangd/issues/310
 llvm::Expected<std::vector<FoldingRange>> getFoldingRanges(ParsedAST &AST) {
   syntax::Arena A;
   syntax::TokenBufferTokenManager TM(AST.getTokens(), AST.getLangOpts(),
                                      AST.getSourceManager());
   const auto *SyntaxTree = syntax::buildSyntaxTree(A, TM, AST.getASTContext());
   return collectFoldingRanges(SyntaxTree, TM);
 }
 
+// FIXME(kirillbobyrev): Collect comments, PP conditional regions, includes and
+// other code regions (e.g. public/private/protected sections of classes,
+// control flow statement bodies).
+// Related issue: https://github.com/clangd/clangd/issues/310
+llvm::Expected<std::vector<FoldingRange>>
+getFoldingRanges(const std::string &Code) {
+  auto OrigStream = clang::pseudo::lex(Code, clang::pseudo::genericLangOpts());
+
+  auto DirectiveStructure = clang::pseudo::DirectiveTree::parse(OrigStream);
+  clang::pseudo::chooseConditionalBranches(DirectiveStructure, OrigStream);
+
+  // FIXME: Provide ranges in the disabled-PP regions as well.
+  auto Preprocessed = DirectiveStructure.stripDirectives(OrigStream);
+
+  auto ParseableStream = cook(Preprocessed, clang::pseudo::genericLangOpts());
+  pseudo::pairBrackets(ParseableStream);
+
+  std::vector<FoldingRange> Result;
+  for (const auto &Tok : ParseableStream.tokens()) {
+    if (auto *Paired = Tok.pair()) {
+      // Process only token at the start of the range. Avoid ranges on a single
+      // line.
+      if (Tok.Line < Paired->Line) {
+        Position Start = offsetToPosition(
+            Code,
+            OrigStream.tokens()[Tok.OriginalIndex].text().data() - Code.data());
+        Position End = offsetToPosition(
+            Code, OrigStream.tokens()[Paired->OriginalIndex].text().data() -
+                      Code.data());
+        FoldingRange FR;
+        FR.startLine = Start.line;
+        FR.startCharacter = Start.character + 1;
+        FR.endLine = End.line;
+        FR.endCharacter = End.character;
+        Result.push_back(FR);
+      }
+    }
+  }
+  return Result;
+}
+
 } // namespace clangd
 } // namespace clang

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

const char *Tests[] = {
           void getFooBar() { }
         };
       )cpp",
   };
   for (const char *Test : Tests) {
     auto T = Annotations(Test);
     auto AST = TestTU::withCode(T.code()).build();
     EXPECT_THAT(gatherFoldingRanges(llvm::cantFail(getFoldingRanges(AST))),
                 UnorderedElementsAreArray(T.ranges()))
         << Test;
   }
 }
 
+TEST(FoldingRangesPseudoParser, All) {
+  const char *Tests[] = {
+      R"cpp(
+        #define FOO int foo() {\
+          int Variable = 42; \
+        }
+
+        // Do not generate folding range for braces within macro expansion.
+        FOO
+
+        // Do not generate folding range within macro arguments.
+        #define FUNCTOR(functor) functor
+        void func() {[[
+          FUNCTOR([](){});
+        ]]}
+
+        // Do not generate folding range with a brace coming from macro.
+        #define LBRACE {
+        void bar() LBRACE
+          int X = 42;
+        }
+      )cpp",
+      R"cpp(
+        void func() {[[
+          int Variable = 100;
+
+          if (Variable > 5) {[[
+            Variable += 42;
+          ]]} else if (Variable++)
+            ++Variable;
+          else {[[
+            Variable--;
+          ]]}
+
+          // Do not generate FoldingRange for empty CompoundStmts.
+          for (;;) {}
+
+          // If there are newlines between {}, we should generate one.
+          for (;;) {[[
+
+          ]]}
+        ]]}
+      )cpp",
+      R"cpp(
+        class Foo {[[
+        public:
+          Foo() {[[
+            int X = 1;
+          ]]}
+
+        private:
+          int getBar() {[[
+            return 42;
+          ]]}
+
+          // Braces are located at the same line: no folding range here.
+          void getFooBar() { }
+        ]]};
+      )cpp",
+      R"cpp(
+        // Range boundaries on escaped newlines.
+        class Foo \
+        \
+        {[[  \
+        public:
+          Foo() {[[\
+            int X = 1;
+          ]]}   \
+        ]]};
+      )cpp",
+  };
+  for (const char *Test : Tests) {
+    auto T = Annotations(Test);
+    EXPECT_THAT(
+        gatherFoldingRanges(llvm::cantFail(getFoldingRanges(T.code().str()))),
+        UnorderedElementsAreArray(T.ranges()))
+        << Test;
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

clang-tools-extra/pseudo/include/clang-pseudo/Token.h

struct Token {
 
   /// Zero-based line number for the start of the token.
   /// This refers to the original source file as written.
   uint32_t Line = 0;
   /// Width of whitespace before the first token on this line.
   uint8_t Indent = 0;
   /// Flags have some meaning defined by the function that produced this stream.
   uint8_t Flags = 0;
+  /// Index into the original token stream (as raw-lexed from the source code).
+  Index OriginalIndex = Invalid;
   // Helpers to get/set Flags based on `enum class`.
   template <class T> bool flag(T Mask) const {
     return Flags & uint8_t{static_cast<std::underlying_type_t<T>>(Mask)};
   }
   template <class T> void setFlag(T Mask) {
     Flags |= uint8_t{static_cast<std::underlying_type_t<T>>(Mask)};
   }
 
struct Token {
   /// Returns the bracket paired with this one, if any.
   const Token *pair() const { return Pair == 0 ? nullptr : this + Pair; }
 
   /// The type of token as determined by clang's lexer.
   clang::tok::TokenKind Kind = clang::tok::unknown;
   /// If this token is a paired bracket, the offset of the pair in the stream.
   int32_t Pair = 0;
 };
-static_assert(sizeof(Token) <= sizeof(char *) + 20, "Careful with layout!");
+static_assert(sizeof(Token) <= sizeof(char *) + 24, "Careful with layout!");
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Token &);
 
 /// A half-open range of tokens within a stream.
 struct Token::Range {
   Index Begin = 0;
   Index End = 0;
 
   uint32_t size() const { return End - Begin; }
public:
   }
 
   /// May return the end sentinel if the stream is empty.
   const Token &front() const {
     assert(isFinalized());
     return Storage[1];
   }
 
   /// Returns the shared payload.
   std::shared_ptr<void> getPayload() const { return Payload; }
   /// Adds the given payload to the stream.
   void addPayload(std::shared_ptr<void> P) {
     if (!Payload)
       Payload = std::move(P);
     else
       Payload = std::make_shared<
           std::pair<std::shared_ptr<void>, std::shared_ptr<void>>>(
           std::move(P), std::move(Payload));
   }
 
   /// Print the tokens in this stream to the output stream.
   ///
   /// The presence of newlines/spaces is preserved, but not the quantity.

clang-tools-extra/pseudo/lib/CMakeLists.txt

add_clang_library(clangPseudo
   Lex.cpp
   Token.cpp
 
   LINK_LIBS
   clangBasic
   clangLex
   clangPseudoGrammar
   )
+
+  target_include_directories(clangPseudo INTERFACE
+  $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/../include>
+  )

clang-tools-extra/pseudo/lib/Lex.cpp

TokenStream lex(const std::string &Code, const clang::LangOptions &LangOpts) {
   // Tokenize using clang's lexer in raw mode.
   // std::string guarantees null-termination, which the lexer needs.
   clang::Lexer Lexer(Start, LangOpts, Code.data(), Code.data(),
                      Code.data() + Code.size());
   Lexer.SetCommentRetentionState(true);
 
   TokenStream Result;
   clang::Token CT;
+  // Index into the token stream of original source code.
+  Token::Index TokenIndex = 0;
   unsigned LastOffset = 0;
   unsigned Line = 0;
   unsigned Indent = 0;
   for (Lexer.LexFromRawLexer(CT); CT.getKind() != clang::tok::eof;
        Lexer.LexFromRawLexer(CT)) {
     unsigned Offset =
         CT.getLocation().getRawEncoding() - Start.getRawEncoding();
 
for (Lexer.LexFromRawLexer(CT); CT.getKind() != clang::tok::eof;
     Tok.Indent = Indent;
     Tok.Line = Line;
 
     if (CT.isAtStartOfLine())
       Tok.setFlag(LexFlags::StartsPPLine);
     if (CT.needsCleaning() || CT.hasUCN())
       Tok.setFlag(LexFlags::NeedsCleaning);
 
+    Tok.OriginalIndex = TokenIndex++;
     Result.push(Tok);
     LastOffset = Offset;
   }
   Result.finalize();
   return Result;
 }
 
 TokenStream cook(const TokenStream &Code, const LangOptions &LangOpts) {

clang-tools-extra/pseudo/unittests/TokenTest.cpp

 }
 
 MATCHER_P(hasFlag, Flag, "") { return arg.flag(Flag); }
 
 MATCHER_P2(lineIndent, Line, Indent, "") {
   return arg.Line == (unsigned)Line && arg.Indent == (unsigned)Indent;
 }
 
+MATCHER_P(originalIndex, index, "") {
+  return arg.OriginalIndex == (Token::Index)index;
+}
+
 TEST(TokenTest, Lex) {
   LangOptions Opts;
   std::string Code = R"cpp(
     #include <stdio.h>
     int main() {
       return 42; // the answer
     }
   )cpp";

 two \
 tokens
   )cpp";
   TokenStream Raw = lex(Code, Opts);
   EXPECT_THAT(
       Raw.tokens(),
       ElementsAre(AllOf(token("one_\\\ntoken", tok::raw_identifier),
                         hasFlag(LexFlags::StartsPPLine),
-                        hasFlag(LexFlags::NeedsCleaning), lineIndent(1, 0)),
+                        hasFlag(LexFlags::NeedsCleaning), lineIndent(1, 0),
+                        originalIndex(0)),
                   AllOf(token("two", tok::raw_identifier),
                         hasFlag(LexFlags::StartsPPLine),
-                        Not(hasFlag(LexFlags::NeedsCleaning))),
+                        Not(hasFlag(LexFlags::NeedsCleaning)),
+                        originalIndex(1)),
                   AllOf(token("\\\ntokens", tok::raw_identifier),
                         Not(hasFlag(LexFlags::StartsPPLine)),
-                        hasFlag(LexFlags::NeedsCleaning))));
+                        hasFlag(LexFlags::NeedsCleaning), originalIndex(2))));
 
   TokenStream Cooked = cook(Raw, Opts);
   EXPECT_THAT(
       Cooked.tokens(),
-      ElementsAre(AllOf(token("one_token", tok::identifier), lineIndent(1, 0)),
-                  token("two", tok::identifier),
-                  token("tokens", tok::identifier)));
+      ElementsAre(AllOf(token("one_token", tok::identifier), lineIndent(1, 0),
+                        originalIndex(0)),
+                  AllOf(token("two", tok::identifier), originalIndex(1)),
+                  AllOf(token("tokens", tok::identifier), originalIndex(2))));
 }
 
 TEST(TokenTest, EncodedCharacters) {
   LangOptions Opts;
   Opts.Trigraphs = true;
   Opts.Digraphs = true;
   Opts.C99 = true; // UCNs
   Opts.CXXOperatorNames = true;

 >> // split
 // >> with an escaped newline in the middle, split
 >\
 >
 >>= // not split
 )cpp";
   TokenStream Cook = cook(lex(Code, Opts), Opts);
   TokenStream Split = stripComments(Cook);
-  EXPECT_THAT(Split.tokens(), ElementsAreArray({
-                                  token(">", tok::greater),
-                                  token(">", tok::greater),
-                                  token(">", tok::greater),
-                                  token(">", tok::greater),
-                                  token(">>=", tok::greatergreaterequal),
-                              }));
+  EXPECT_THAT(Split.tokens(),
+              ElementsAre(AllOf(token(">", tok::greater), originalIndex(0)),
+                          AllOf(token(">", tok::greater), originalIndex(0)),
+                          // Token 1 and 2 are comments.
+                          AllOf(token(">", tok::greater), originalIndex(3)),
+                          AllOf(token(">", tok::greater), originalIndex(3)),
+                          AllOf(token(">>=", tok::greatergreaterequal),
+                                originalIndex(4))));
 }
 
 TEST(TokenTest, DropComments) {
   LangOptions Opts;
   std::string Code = R"cpp(
   // comment
   int /*abc*/;
 )cpp";
   TokenStream Raw = cook(lex(Code, Opts), Opts);
   TokenStream Stripped = stripComments(Raw);
-  EXPECT_THAT(Raw.tokens(),
-              ElementsAreArray(
-                  {token("// comment", tok::comment), token("int", tok::kw_int),
-                   token("/*abc*/", tok::comment), token(";", tok::semi)}));
-
-  EXPECT_THAT(Stripped.tokens(), ElementsAreArray({token("int", tok::kw_int),
-                                                   token(";", tok::semi)}));
+  EXPECT_THAT(
+      Raw.tokens(),
+      ElementsAre(AllOf(token("// comment", tok::comment), originalIndex(0)),
+                  AllOf(token("int", tok::kw_int), originalIndex(1)),
+                  AllOf(token("/*abc*/", tok::comment), originalIndex(2)),
+                  AllOf(token(";", tok::semi), originalIndex(3))));
+
+  EXPECT_THAT(Stripped.tokens(),
+              ElementsAre(AllOf(token("int", tok::kw_int), originalIndex(1)),
+                          AllOf(token(";", tok::semi), originalIndex(3))));
 }
 
 } // namespace
 } // namespace pseudo
 } // namespace clang