[Tooling/Syntax] Helpers to find spelled tokens touching a location.

[sammccall]

Summary

Useful when positions are used to target nodes, with before/after ambiguity.

[kbobyrev]

clang/include/clang/Tooling/Syntax/Tokens.h

320

Maybe llvm::Optional<> here?

clang/lib/Tooling/Syntax/Tokens.cpp

254

Nit: maybe mention this requirement in the header comment?

257

Nit: "Comparing SourceLocations within one file using operator less/< is a valid operation"? Can't come up with something better, but this is slightly hard to understand.

262

Nit: static casts here or in variable declarations?

267

The formatting looks weird here, does it come from Clang-Format?

[merge_guards_bot]

Unit tests: pass. 60699 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

[sammccall]

comments

clang/include/clang/Tooling/Syntax/Tokens.h

320

Pointers are the idiomatic way to express "optional, by-reference" in LLVM.

By contrast, optional<Token&> is illegal, and optional<token*> is unidiomatic

clang/lib/Tooling/Syntax/Tokens.cpp

254

It is mentioned - Loc must be a spelling location.

257

done (I think). FileID rather than file here, because it's not true (or at least not clear) about files.

262

Replaced with an explicit ternary instead, which is (maybe) clearer?

[merge_guards_bot]

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

clang-format: pass.

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

[kbobyrev]

clang/include/clang/Tooling/Syntax/Tokens.h

320

Ah, I see, I thought a copy is quite cheap in this case. Makes sense then.

clang/lib/Tooling/Syntax/Tokens.cpp

254

Ah, okay, I didn't know that spelling location implies exactly this property, my bad.

[ilya-biryukov]

clang/lib/Tooling/Syntax/Tokens.cpp

270

NIT: add braces around if statement

[ilya-biryukov]

clang/lib/Tooling/Syntax/Tokens.cpp

260

NIT: why not Right->location() <= Loc instead of !(Loc < Right->location)?
Do we only overload operator < for SourceLocations?

261

Maybe compare offsets instead of locations?
It might be more code, but it would read much cleaner.

It always feels weird to compare source locations for anything other than storing them in std::map

[kbobyrev]

clang/lib/Tooling/Syntax/Tokens.cpp

260

Yes, we only have operator< :(

[sammccall]

Add overloads for SourceLocation comparison, and document when they're meaningful.

[sammccall]

braces

clang/include/clang/Tooling/Syntax/Tokens.h

320

Ah, it is, so Optional<Token> would be an option. But the address is meaningful - spelled tokens have contiguous storage that indicates their sequence. So returning a pointer is actually more useful.

clang/lib/Tooling/Syntax/Tokens.cpp

261

I find the SM.getFileOffset(...) everywhere pretty hard to read and obscures the actual locations.
But agree about the operators, I've added the rest. Having operator< is pretty evil, but I don't think the others are particularly incrementally evil.

270

Is there some reference for preferred LLVM style for this, or personal preference? (Real question, as this comes up a bunch)

I ask because that's my *least*-preferred option - no braces > braces on for > braces on both > braces on (only) if.

Added braces to the for (maybe that's what you meant?)

[merge_guards_bot]

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

clang-format: pass.

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

[kbobyrev]

clang/lib/Tooling/Syntax/Tokens.cpp

270

I guess it's a personal preference (also for me), but I don't think there is a strict guideline on that. Interestingly enough, I think there is a piece of code in the styleguide that looks exactly like the code you had: https://llvm.org/docs/CodingStandards.html#turn-predicate-loops-into-predicate-functions

Some Clang subprojects tend to put braces everywhere though.

That being said, I guess no braces at all would be the best option here.

[ilya-biryukov]

clang/lib/Tooling/Syntax/Tokens.cpp

261

I find it to be the only way to write code, which unambiguously says what it wants to do with source locations.

Not saying it's pretty, but I the source location API was designed to be used this way. Arguably, using something else in special corner cases does more harm than good (hard-to-read, non-conventional code).

But up to you.

270

Not sure if it's in LLVM style guide, but files inside Syntax folder definitely use this style: put braces everywhere until you reach the last level of nesting for non-leaf statements (i.e. having other statements as children, e.g. loops,. if statements, etc)

It's my personal preference, happy to discuss whether having this makes sense.

[ilya-biryukov]

clang/lib/Tooling/Syntax/Tokens.cpp

270

Yeah, so LLVM style is unclear, but has examples with no braces.
Could be the argument to get rid of those.

I'd still stick to my personal preferences where I can, but if everyone thinks no braces is better, happy to go with this option.

[merge_guards_bot]

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

clang-format: pass.

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

[sammccall]

clang/lib/Tooling/Syntax/Tokens.cpp

261

But up to you.

I would rather use the operators, with the comment for the unusual usage, if that's OK.

(I agree it doesn't generalize and about the intent of the APIs, but think the APIs hurt readability to the extent that there's less value in consistency than in clear intent at individual callsites).

270

I think we're good here - I'm fine with the braces on for, and it sounds like that's what you wanted.
(I guess I misread "braces around if statement" as "braces around if body")

[ilya-biryukov]

clang/lib/Tooling/Syntax/Tokens.cpp

270

Ah, great, we're on the same page then!

clang/include/clang/Basic/SourceLocation.h

 inline bool operator==(const SourceLocation &LHS, const SourceLocation &RHS) {
   return LHS.getRawEncoding() == RHS.getRawEncoding();
 }
 
 inline bool operator!=(const SourceLocation &LHS, const SourceLocation &RHS) {
   return !(LHS == RHS);
 }
 
+// Ordering is meaningful only if LHS and RHS have the same FileID!
+// Otherwise use SourceManager::isBeforeInTranslationUnit().
 inline bool operator<(const SourceLocation &LHS, const SourceLocation &RHS) {
   return LHS.getRawEncoding() < RHS.getRawEncoding();
 }
+inline bool operator>(const SourceLocation &LHS, const SourceLocation &RHS) {
+  return LHS.getRawEncoding() > RHS.getRawEncoding();
+}
+inline bool operator<=(const SourceLocation &LHS, const SourceLocation &RHS) {
+  return LHS.getRawEncoding() <= RHS.getRawEncoding();
+}
+inline bool operator>=(const SourceLocation &LHS, const SourceLocation &RHS) {
+  return LHS.getRawEncoding() >= RHS.getRawEncoding();
+}
 
 /// A trivial tuple used to represent a source range.
 class SourceRange {
   SourceLocation B;
   SourceLocation E;
 
 public:
   SourceRange() = default;

clang/include/clang/Tooling/Syntax/Tokens.h

private:
   /// #file, etc.).
   std::vector<syntax::Token> ExpandedTokens;
   llvm::DenseMap<FileID, MarkedFile> Files;
   // The value is never null, pointer instead of reference to avoid disabling
   // implicit assignment operator.
   const SourceManager *SourceMgr;
 };
 
+/// The spelled tokens that overlap or touch a spelling location Loc.
+/// This always returns 0-2 tokens.
+llvm::ArrayRef<syntax::Token>
+spelledTokensTouching(SourceLocation Loc, const syntax::TokenBuffer &Tokens);
+
+/// The identifier token that overlaps or touches a spelling location Loc.
+/// If there is none, returns nullptr.
+const syntax::Token *
+spelledIdentifierTouching(SourceLocation Loc,
+                          const syntax::TokenBuffer &Tokens);
+
 /// Lex the text buffer, corresponding to \p FID, in raw mode and record the
 /// resulting spelled tokens. Does minimal post-processing on raw identifiers,
 /// setting the appropriate token kind (instead of the raw_identifier reported
 /// by lexer in raw mode). This is a very low-level function, most users should
 /// prefer to use TokenCollector. Lexing in raw mode produces wildly different
 /// results from what one might expect when running a C++ frontend, e.g.
 /// preprocessor does not run at all.
 /// The result will *not* have a 'eof' token at the end.

clang/lib/Tooling/Syntax/Tokens.cpp

TokenBuffer::expansionStartingAt(const syntax::Token *Spelled) const {
   Expansion E;
   E.Spelled = llvm::makeArrayRef(File.SpelledTokens.data() + M->BeginSpelled,
                                  File.SpelledTokens.data() + M->EndSpelled);
   E.Expanded = llvm::makeArrayRef(ExpandedTokens.data() + M->BeginExpanded,
                                   ExpandedTokens.data() + M->EndExpanded);
   return E;
 }
 
+llvm::ArrayRef<syntax::Token>
+syntax::spelledTokensTouching(SourceLocation Loc,
+                              const syntax::TokenBuffer &Tokens) {
+  assert(Loc.isFileID());
+  llvm::ArrayRef<syntax::Token> All =
+      Tokens.spelledTokens(Tokens.sourceManager().getFileID(Loc));
+  // Comparing SourceLocations is well-defined within a FileID.
+  auto *Right = llvm::partition_point(
+      All, [&](const syntax::Token &Tok) { return Tok.location() < Loc; });
+  bool AcceptRight = Right != All.end() && Right->location() <= Loc;
+  bool AcceptLeft = Right != All.begin() && (Right - 1)->endLocation() >= Loc;
+  return llvm::makeArrayRef(Right - (AcceptLeft ? 1 : 0),
+                            Right + (AcceptRight ? 1 : 0));
+}
+
+const syntax::Token *
+syntax::spelledIdentifierTouching(SourceLocation Loc,
+                                  const syntax::TokenBuffer &Tokens) {
+  for (const syntax::Token &Tok : spelledTokensTouching(Loc, Tokens)) {
+    if (Tok.kind() == tok::identifier)
+      return &Tok;
+  }
+  return nullptr;
+}
+
 std::vector<const syntax::Token *>
 TokenBuffer::macroExpansions(FileID FID) const {
   auto FileIt = Files.find(FID);
   assert(FileIt != Files.end() && "file not tracked by token buffer");
   auto &File = FileIt->second;
   std::vector<const syntax::Token *> Expansions;
   auto &Spelled = File.SpelledTokens;
   for (auto Mapping : File.Mappings) {

clang/unittests/Tooling/Syntax/TokensTest.cpp

TEST_F(TokenBufferTest, macroExpansions) {
   for (auto Range : Code.ranges("macro"))
     ExpectedMacroRanges.push_back(
         FileRange(SM.getMainFileID(), Range.Begin, Range.End));
   std::vector<FileRange> ActualMacroRanges;
   for (auto Expansion : Expansions)
     ActualMacroRanges.push_back(Expansion->range(SM));
   EXPECT_EQ(ExpectedMacroRanges, ActualMacroRanges);
 }
+
+TEST_F(TokenBufferTest, Touching) {
+  llvm::Annotations Code("^i^nt^ ^a^b^=^1;^");
+  recordTokens(Code.code());
+
+  auto Touching = [&](int Index) {
+    SourceLocation Loc = SourceMgr->getComposedLoc(SourceMgr->getMainFileID(),
+                                                   Code.points()[Index]);
+    return spelledTokensTouching(Loc, Buffer);
+  };
+  auto Identifier = [&](int Index) {
+    SourceLocation Loc = SourceMgr->getComposedLoc(SourceMgr->getMainFileID(),
+                                                   Code.points()[Index]);
+    const syntax::Token *Tok = spelledIdentifierTouching(Loc, Buffer);
+    return Tok ? Tok->text(*SourceMgr) : "";
+  };
+
+  EXPECT_THAT(Touching(0), SameRange(findSpelled("int")));
+  EXPECT_EQ(Identifier(0), "");
+  EXPECT_THAT(Touching(1), SameRange(findSpelled("int")));
+  EXPECT_EQ(Identifier(1), "");
+  EXPECT_THAT(Touching(2), SameRange(findSpelled("int")));
+  EXPECT_EQ(Identifier(2), "");
+
+  EXPECT_THAT(Touching(3), SameRange(findSpelled("ab")));
+  EXPECT_EQ(Identifier(3), "ab");
+  EXPECT_THAT(Touching(4), SameRange(findSpelled("ab")));
+  EXPECT_EQ(Identifier(4), "ab");
+
+  EXPECT_THAT(Touching(5), SameRange(findSpelled("ab =")));
+  EXPECT_EQ(Identifier(5), "ab");
+
+  EXPECT_THAT(Touching(6), SameRange(findSpelled("= 1")));
+  EXPECT_EQ(Identifier(6), "");
+
+  EXPECT_THAT(Touching(7), SameRange(findSpelled(";")));
+  EXPECT_EQ(Identifier(7), "");
+
+  ASSERT_EQ(Code.points().size(), 8u);
+}
+
 } // namespace