[PATCH] D87891: [clangd] findNearbyIdentifier(): guaranteed to give up after 2^N lines

[Aleksandr Platonov via Phabricator via cfe-commits]

ArcsinX updated this revision to Diff 292739.
ArcsinX added a comment.

Fix format


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D87891/new/

https://reviews.llvm.org/D87891

Files:
  clang-tools-extra/clangd/XRefs.cpp


Index: clang-tools-extra/clangd/XRefs.cpp
===================================================================
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -563,23 +563,46 @@
     assert(SM.getFileID(Loc) == File && "spelled token in wrong file?");
     unsigned Line = SM.getSpellingLineNumber(Loc);
     if (Line > WordLine)
-      return 1 + llvm::Log2_64(Line - WordLine);
+      return 1 + Line - WordLine;
     if (Line < WordLine)
-      return 2 + llvm::Log2_64(WordLine - Line);
+      return 2 + WordLine - Line;
     return 0;
   };
   const syntax::Token *BestTok = nullptr;
   // Search bounds are based on word length: 2^N lines forward.
-  unsigned BestCost = Word.Text.size() + 1;
+  unsigned BestCost = std::pow(2, Word.Text.size());
+  auto Code = SM.getBuffer(File)->getBuffer();
+  unsigned FileLines = std::count(Code.begin(), Code.end(), '\n');
+  // Min position:
+  // - Line: max(0, WordLine - 2^N)
+  // - Column: 0
+  auto OffsetMin = positionToOffset(
+      Code,
+      {static_cast<int>(WordLine < BestCost ? 0 : WordLine - BestCost), 0},
+      /*AllowColumnBeyondLineLength=*/true);
+  assert(OffsetMin);
+  auto LocMin = SM.getLocForStartOfFile(File).getLocWithOffset(*OffsetMin);
+  // Max position:
+  // - Line: min(<number of lines in the file>, WordLine + 2^N + 1)
+  // - Column: 0
+  auto OffsetMax =
+      positionToOffset(Code,
+                       {static_cast<int>(WordLine + BestCost + 1 < FileLines
+                                             ? WordLine + BestCost + 1
+                                             : FileLines),
+                        0},
+                       /*AllowColumnBeyondLineLength=*/true);
+  assert(OffsetMax);
+  auto LocMax = SM.getLocForStartOfFile(File).getLocWithOffset(*OffsetMax);
 
   // Updates BestTok and BestCost if Tok is a good candidate.
   // May return true if the cost is too high for this token.
   auto Consider = [&](const syntax::Token &Tok) {
+    if (Tok.location() < LocMin || Tok.location() > LocMax)
+      return true; // we are too far from the word, break the outer loop.
     if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text))
       return false;
-    // No point guessing the same location we started with.
-    if (Tok.location() == Word.Location)
-      return false;
+
     // We've done cheap checks, compute cost so we can break the caller's loop.
     unsigned TokCost = Cost(Tok.location());
     if (TokCost >= BestCost)



Index: clang-tools-extra/clangd/XRefs.cpp
===================================================================
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -563,23 +563,46 @@
     assert(SM.getFileID(Loc) == File && "spelled token in wrong file?");
     unsigned Line = SM.getSpellingLineNumber(Loc);
     if (Line > WordLine)
-      return 1 + llvm::Log2_64(Line - WordLine);
+      return 1 + Line - WordLine;
     if (Line < WordLine)
-      return 2 + llvm::Log2_64(WordLine - Line);
+      return 2 + WordLine - Line;
     return 0;
   };
   const syntax::Token *BestTok = nullptr;
   // Search bounds are based on word length: 2^N lines forward.
-  unsigned BestCost = Word.Text.size() + 1;
+  unsigned BestCost = std::pow(2, Word.Text.size());
+  auto Code = SM.getBuffer(File)->getBuffer();
+  unsigned FileLines = std::count(Code.begin(), Code.end(), '\n');
+  // Min position:
+  // - Line: max(0, WordLine - 2^N)
+  // - Column: 0
+  auto OffsetMin = positionToOffset(
+      Code,
+      {static_cast<int>(WordLine < BestCost ? 0 : WordLine - BestCost), 0},
+      /*AllowColumnBeyondLineLength=*/true);
+  assert(OffsetMin);
+  auto LocMin = SM.getLocForStartOfFile(File).getLocWithOffset(*OffsetMin);
+  // Max position:
+  // - Line: min(<number of lines in the file>, WordLine + 2^N + 1)
+  // - Column: 0
+  auto OffsetMax =
+      positionToOffset(Code,
+                       {static_cast<int>(WordLine + BestCost + 1 < FileLines
+                                             ? WordLine + BestCost + 1
+                                             : FileLines),
+                        0},
+                       /*AllowColumnBeyondLineLength=*/true);
+  assert(OffsetMax);
+  auto LocMax = SM.getLocForStartOfFile(File).getLocWithOffset(*OffsetMax);
 
   // Updates BestTok and BestCost if Tok is a good candidate.
   // May return true if the cost is too high for this token.
   auto Consider = [&](const syntax::Token &Tok) {
+    if (Tok.location() < LocMin || Tok.location() > LocMax)
+      return true; // we are too far from the word, break the outer loop.
     if (!(Tok.kind() == tok::identifier && Tok.text(SM) == Word.Text))
       return false;
-    // No point guessing the same location we started with.
-    if (Tok.location() == Word.Location)
-      return false;
+
     // We've done cheap checks, compute cost so we can break the caller's loop.
     unsigned TokCost = Cost(Tok.location());
     if (TokCost >= BestCost)

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits